Distributing Candies

Problem Description

There are $n$ children standing in a queue waiting for the teacher to hand out candies. The $i$-th child wants at least $a_i$ candies, and the number of candies given to him must be strictly greater than the number given to the previous child, otherwise he will be unhappy.

The teacher wants to know the minimum total number of candies needed to keep all children happy. Can you help?

Input Format

The first line contains a positive integer $n$, the number of children.

The second line contains $n$ positive integers $a_1, a_2, \ldots, a_n$, the minimum number of candies each child needs, in order.

Output Format

Output one line containing one integer: the minimum total number of candies needed.

Sample Input 1

4
1 4 3 3

Sample Input 2

15
314 15926 53589793 238462643 383279502 8 8 4 1 9 7 1 6 9 3

Sample Output 1

16

Sample Output 2

4508143253

Sample Explanation

For the first sample, there are $4$ children needing $1, 4, 3, 3$ candies. To satisfy the requirements, the teacher can distribute as follows:

• Child 1 gets $1$ (at least $1$, and no predecessor, so $1$);
• Child 2 needs at least $4$ and must exceed child 1's $1$, so give $4$;
• Child 3 needs at least $3$ and must exceed child 2's $4$, so give $5$;
• Child 4 needs at least $3$ and must exceed child 3's $5$, so give $6$.

Total: $1 + 4 + 5 + 6 = 16$, which is the minimum.

Constraints

For all test cases, $1 \le n \le 1000$ and $1 \le a_i \le 10^9$ are guaranteed.