SOLVE

LATER

Number Sum

/

Alice is given an array of $$N$$ integers. Now, she is playing a game with Bob. In one turn Alice picks a sub-array of the given array $$A$$. In every turn, she picks a new subarray i.e. one with either different starting index or different ending index from the subarrays picked before.

Now, Bob starts shouting the natural numbers from beginning i.e. he first says $$1$$ then $$2$$ and so on. Alice stops him at the first integer which does not appear in the subarray that she has picked in this turn. Later on, she asks Bob to write the sum of all the values in which she stops him on a paper. Bob is weak in maths, can you help him?

**Note: **Please go through the sample carefully.

**Input Format**

The first line contains a single integer $$N$$. The next line contains $$N$$ space-separated integers, where the $$i$$-th integer denotes $$ A[i] $$.

**Output Format**

Print the single integer representing the required result.

**Constraints**

$$ 1 \le N \le 5 000 $$

$$ 1 \le A[i] \le 10^9 $$

Explanation

Since, Alice can pick any subarray in any order. So let's find out the answer for each subarray and then add it.

Array = $$[1\;2\;3]$$

In the below lines $$[a , b]$$ denotes the subarray that inclues all elements in the range $$[a , b]$$:

$$[1 , 1] = 2$$

$$[1 , 2] = 3$$

$$[1 , 3] = 4$$

$$[2 , 2] = 1$$

$$[2 , 3] = 1$$

$$[3 , 3] = 1$$

So, the answer is $$2 + 3 + 4 + 1 + 1 + 1 = 12$$

Time Limit:
1.0 sec(s)
for each input file.

Memory Limit:
256 MB

Source Limit:
1024 KB

Initializing Code Editor...