Clearing the Track

Time limit1sMemory limit1024 MB

Summary

Given a circular track where each pickup reverses direction, find the total distance Dalgu walks until all trash is removed.

Level: Medium5 of 10
Topics: Math, Simulation, Array
Solved: No attempts yet

Problem

The day after the DGIST sports day, Dalgu decides to clean up a circular running track of length $N$ that is full of trash.

The track has $N$ zones numbered 1 to $N$ clockwise around its circumference, and each zone is 1 unit apart. Zone $i$ holds $A_i$ pieces of trash. Dalgu wants to remove all the trash from every zone, and to pass the time, Dalgu removes it in the following way.

Dalgu starts at zone 1, which has no trash, and moves clockwise.
If the zone reached has no trash, Dalgu keeps moving in the same direction.
If the zone reached has trash, Dalgu removes one piece from that zone and reverses the direction of movement.
Once all the trash in every zone is removed, Dalgu finishes and stops moving.

Input

The first line contains the number of zones $N$ . ( $2 \le N \le 200\,000$ )

The second line contains the amounts of trash $A_1, A_2, \cdots, A_N$ in each zone, separated by spaces. ( $0 \le A_i \le 10\,000$ , $A_1 = 0$ )

Output

Print the total distance Dalgu travels while following the rules above.

Examples3

Example 1
Input
```
5
0 2 0 1 1
```
Expected output
```
8
```
Example 2
Input
```
3
0 1 5
```
Expected output
```
15
```
Example 3
Input
```
6
0 5 3 2 5 2
```
Expected output
```
55
```