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 $$
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$$
