The Good Ranges

★★★★★

4.5

11 votes

Implementation, Basic Programming, Easy, Standard template library (STL), Basics of Implementation

Details

Submissions

Discussion

Editorial

Problem

Consider you have a set $A$ . A Good Range is the largest range that contains only one element from the set $A$ .

Now you are provided with the number range $1$ to $N$ and $M$ queries. In each query, an integer $X$ is added to set $A$ and for each query, you have to output the sum of left and right border indices of all the Good Ranges.

For example. $N$ = $10$ , and in the first query $2$ is added to set . The Good Ranges contain the range $[1,10]$ and the sum is $11$ . Here $[2,2]$ is also a range containing only one element from the set but it isn't the largest one. Now suppose $5$ is added to the set, then the largest range containing only $2$ is $[1,4]$ and largest containing only $5$ is $[3,10]$ , so the sum is $1+4+3+10 = 18$ .

Note: Set contains only distinct elements.

INPUT:

The first line contains two integers $N$ and $M$ .
Next, $M$ lines contain one integer $X$

OUTPUT:

For each query print one integer, the sum of all the border indices of the Good Ranges.

Note: Queries may have some numbers repeated.

CONSTRAINTS:

$1 \le N,M \le 10^6$
$1 \le X \le N$

Time Limit: 2

Memory Limit: 256

Source Limit:

Explanation

First $2$ is added to the set and the largest range containing only $2$ is $[1,10]$ .

Then $7$ is added and the range containing only $2$ becomes $[1,6]$ and containing only $7$ becomes $[3,10]$ .

Then $5$ is added and the ranges are:

For $2$ : $[1,4]$

For $5$ : $[3,6]$

For $7$ : $[6,10]$

Similarly for all other queries.