Banks

Wall Street in Wonderland has $n$ banks standing in a circle, so every bank has one left neighbour and one right neighbour. The left neighbour of the first bank is the last bank, and the right neighbour of the last bank is the first bank. The banks are numbered from $0$ to $n-1$. The left neighbour of bank $i$ is bank $(i-1+n) \bmod n$ and its right neighbour is bank $(i+1) \bmod n$.

Bank $i$ has capital $k_i$. The capitals of all banks add up to a positive number.

Whenever the capital $k_i$ of some bank $i$ is negative, the Bank Fairy spends one magic move and turns that capital into a positive one. If $k_i = -7$, then $k_i = 7$ after the magic move. Both neighbours pay for it: the capital of the left neighbour and the capital of the right neighbour each drop by $|k_i|$. If the left neighbour held $5$ and the right neighbour held $11$, they hold $-2$ and $4$ after the move.

The drop applies once per neighbour relation. When $n = 2$ the remaining bank is both the left and the right neighbour, so its capital drops by $2|k_i|$. When $n = 1$ the only capital is positive, so no magic move is ever possible.

What is the minimal number of magic moves the Bank Fairy has to make so that the capital of every bank is greater than or equal to $0$?

The first line contains the number of banks $n$ ($0 < n < 10000$).

The second line contains the capitals $k_0, k_1, \dots, k_{n-1}$ in the order in which the banks stand on Wall Street, separated by single spaces. Each capital is an integer with $-32000 < k_i < 32000$, and their sum is positive.

Print the minimal number of magic moves on a single line.