Balancing Bacteria

Farmer John has $N$ ($1\le N\le 2\cdot 10^5$) patches of grass in a line. The bacteria level of patch $i$ differs from the healthy level by $a_i$ ($-10^{15}\le a_i \le 10^{15}$). For example, if $a_i = -3$, then patch $i$ is 3 units below normal, so it needs exactly 3 more units of bacteria to be healthy.

Farmer John wants every patch to reach the healthy level. He has two pesticides, one that adds bacteria and one that removes bacteria. To spray either one, he stands at patch $N$ (the rightmost patch) and chooses a sprayer power $L$ ($1 \leq L \leq N$).

The sprayer affects patches near Farmer John most, and its effect weakens with distance. If he uses the pesticide that adds bacteria, then $L$ units are added to patch $N$, $L-1$ units to patch $N-1$, $L-2$ units to patch $N-2$, and so on. Patches $1 \ldots N-L$ receive nothing because the sprayer does not reach them. The pesticide that removes bacteria works the same way, except it subtracts the amounts instead.

Find the minimum number of times Farmer John must spray so that every patch reaches the healthy bacteria level. The answer is guaranteed to be at most $10^9$.

The values can be very large, so use a 64-bit integer type such as long long in C/C++.

The first line contains $N$.

The second line contains $N$ integers $a_1 \dots a_N$, the initial bacteria levels of the patches of grass.

Print the minimum number of sprays needed to make every patch of grass have the healthy bacteria level.