You want to practise skating on a given course. The course consists of a starting point, $N$ intermediate points, and a finishing point. Practice starts at the starting point with speed $0$, visits intermediate points $1$ through $N$ in increasing order, and ends after reaching the finishing point with speed $0$.

Each intermediate point has a speed limit $V_i$, so you must adjust your speed while travelling so that it does not exceed the limit of the next point you visit. You may increase your speed by as much as you wish, but when slowing down, you may reduce it by only $1$ from your speed at the last point visited. Your speed cannot be $0$ anywhere other than the starting and finishing points. You may also keep your speed unchanged.

The result of your practice equals the sum of your speeds at all points, and you want to maximize it. Given the speed limits of the skating course, find the maximum practice result that can be obtained on that course.

For example, suppose a course has three intermediate points with speed limits $V=[2,3,1]$. If you maintain speed $3$ at intermediate point $2$, it is impossible to adjust your speed to at most $1$ at intermediate point $3$. One possible practice plan is to use speeds $[2,2,1]$, whose sum is $2+2+1=5$. Other possible plans include $[1,1,1]$ and $[1,2,1]$, but their sums do not exceed $5$. Thus, the greatest practice result obtainable on this course is $5$.

Constraints

• All given numbers are integers.
• $1 \le N \le 500000$
• $1 \le V_i \le 1000000000$ ($1 \le i \le N$)

Subtasks

1. 8 points: $N \le 8$, $V_i \le 8$ ($1 \le i \le N$)
2. 12 points: $N \le 500$, $V_i \le 500$ ($1 \le i \le N$)
3. 17 points: $N \le 5000$, $V_i \le 5000$ ($1 \le i \le N$)
4. 10 points: $N \le 5000$
5. 53 points: No additional constraints.

Input

The first line contains $N$.

The second line contains $V_1,V_2,\ldots,V_N$, in order, separated by spaces.

Output

Print the answer on the first line.

Examples

Input 1

3
2 3 1

Output 1

5

Input 2

4
23 7 1 5

Output 2

7