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