Snow-covered path

Latvia has had unusually frequent snow this winter. Last night Mārtiņš cleared the path leading to his house. This morning, when he woke up and looked out the window, the path was covered in snow again.

The path is a straight segment $N$ meters long. The snow covering it is uneven. The first meter is covered by snow $a_1$ centimeters deep, the second meter by $a_2$ centimeters, and so on, up to the last meter, which is covered by $a_N$ centimeters.

Mārtiņš starts clearing the path from the first meter. He scoops up all the snow there with a shovel and throws it up and away from himself. The snow falls back onto the path and covers the nearest few meters with a layer 1 centimeter deep. Consider this example.

Figure 1. A 3 centimeter layer of snow spreads over a 3 meter interval.

After clearing the first meter, Mārtiņš moves on to the second. He throws the snow there up, and it again covers the nearest few meters with a 1 centimeter layer. Then he clears the third meter, the fourth, and so on, until no snow is left on the path. The example continues like this.

Figure 2. Clearing the path. Snow that falls beyond the path stays where it lands.

Each time he throws up $a$ centimeters of snow, Mārtiņš spends $a$ energy units. In the example above, he spends $3 + 2 + 4 + 3 + 3 = 15$ energy units in total.

The first line contains the integer $N$, the length of the path.

The second line contains $N$ integers separated by spaces, $a_1, a_2, \dots, a_N$, which describe the depth of the snow covering the path.

Print one number, the amount of energy Mārtiņš spends.

• $1 \le N \le 1\,000\,000$
• $0 \le a_i \le 1\,000\,000\,000$