Description

“Neither a lender nor a borrower be”—how Bessie wishes she could follow this advice. She already has debt relationships with her $N (1 \leq N \leq 100,000)$ friends: she has either borrowed from them or lent to them. Her $N$ friends are labeled $1 \dots N$ in order.

Settlement day has finally arrived. She knows that the total money her friends owe her is greater than the total money she owes them. Her friends are positioned on a straight line: the $i$-th cow stands at distance $i$ meters from the barn. Bessie plans to walk along this line, collecting money from cows who owe her and repaying cows she owes.

As she moves along the line, she may demand that any cow who owes her repay in full. Whenever she has enough money to fully settle a particular debt she owes, she may pay that cow in full. Cow $i$ owes Bessie $D_i$ yuan $(-1,000 \leq D_i \leq 1,000,D_i \neq 0)$; a negative value means Bessie owes cow $i$ money.

Bessie starts from the barn at position $0$ with no money. What is the minimum distance she must walk to collect all debts owed to her and pay off all debts she owes?

Note: She must finish her walk at the position of the last cow.

Input Format

The first line contains an integer $N$.

Lines $2 \dots N+1$: the $(i+1)$-th line contains an integer $D_i$.

Output Format

A single integer: the minimum distance (in meters) Bessie needs to walk to collect and settle all debts.

5
100
-200
250
-200
200

9

Hint

Input explanation:

$3$ cows owe Bessie money; she owes $2$ cows money. When she finishes settling, she will have $150$ yuan.

Output explanation:

谷仓  100  -200  250 -200  200
 |     |     |    |    |    |
 ***>**+**>*****>**+
                   *            < 贝西有 350 元
             -**<***
             *                  < 贝西有 150 元
             ***>****>****>**+
                             *  < 贝西有 350 元
                       -**<***
                       *     
                       ***>***  < 贝西结束她的行走，有 150 元

Translated by ChatGPT 5