Problem Description

Farmer John has $N$ ($1 \le N \le 2 \cdot 10^5$) grasslands arranged in a row, where the bacterial level of grassland $i$ differs from the healthy bacterial level by $a_i$ ($-10^{15} \le a_i \le 10^{15}$). For example, if $a_i = -3$, the bacterial level of grassland $i$ is $3$ units lower than normal, and it requires exactly $3$ additional units of bacteria to raise it to the level considered healthy.

Farmer John wants to ensure that every grassland is restored to a healthy bacterial level. Conveniently, he has two brands of pesticides that he can spray on his fields, one that adds bacteria and another that removes bacteria. When Farmer John sprays either type of pesticide, he stands on grassland $N$ (the rightmost grassland) and selects a power level $L$ ($1 \le L \le N$) for his sprayer.

The sprayer has the greatest effect on grasslands close to Farmer John, with the effect diminishing with distance. If Farmer John chooses the pesticide that adds bacteria, $L$ units of bacteria will be added to grassland $N$, $L-1$ units to grassland $N-1$, $L-2$ units to grassland $N-2$, and so on. Grasslands $1 \ldots N-L$ will not receive any bacteria because the power setting of the sprayer is not sufficient to reach them. Similarly, if Farmer John chooses the pesticide that removes bacteria, $L$ units of bacteria will be removed from grassland $N$, $L-1$ units from grassland $N-1$, and so on. Again, grasslands $1 \ldots N-L$ will be unaffected.

Determine the minimum number of times Farmer John needs to use the sprayer to ensure that every grassland has the recommended bacterial value for healthy grass. The input guarantees that the answer does not exceed $10^9$.

Note that the integers involved in this problem may require using 64-bit integer types (e.g., "long long" in C/C++).

Input Format

The first line of input contains $N$.

The second line contains $N$ integers $a_1 \ldots a_N$, representing the initial bacterial levels of each grassland.

Output Format

Output a single integer, the minimum number of times the sprayer needs to be used to ensure that every grassland has the recommended bacterial value for healthy grass.

Sample Input and Output

Sample Input #1

2
-1 3

Sample Output #1

6

Sample Input #2

5
1 3 -2 -7 5

Sample Output #2

26

Notes/Hints

Sample Explanation 1

Use the pesticide that removes bacteria with a power level of $1$, five times. Then use the pesticide that adds bacteria with a power level of $2$, once.

Test Point Properties

• Test points $3-5$: $N \le 10^3$, the answer does not exceed $10^3$.
• Test points $6-10$: $N \le 10^3$.
• Test points $11-15$: No additional restrictions.

见题面 Input 部分

见题面 Output 部分