P1599 [USACO09MAR] Payback B (Settlement Day)

“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.

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

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

Input explanation: $3$ cows owe Bessie money; she owes $2$ cows money. When she finishes settling, she will have $150$ yuan. Output explanation: ```plain 谷仓 100 -200 250 -200 200 | | | | | | ***>**+**>*****>**+ * < 贝西有 350 元 -******>****>**+ * < 贝西有 350 元 -***** < 贝西结束她的行走，有 150 元 ``` Translated by ChatGPT 5