Payback

Bessie has borrowed money from, or lent money to, each of her $N$ ($1 \le N \le 100000$) friends, conveniently labeled $1 \dots N$.

Payback day has finally come. In total Bessie is owed more money than she owes. The friends stand in a straight line, friend $i$ standing $i$ meters from the barn. Bessie starts at the barn (position $0$) and walks along the line, collecting money from those who owe her and repaying those she owes.

Each friend $i$ has an integer $D_i$ ($-1000 \le D_i \le 1000$, $D_i \ne 0$): if $D_i > 0$, friend $i$ owes Bessie $D_i$; if $D_i < 0$, Bessie owes friend $i$ the amount $|D_i|$.

When Bessie passes a friend who owes her, she may collect that money at once. She may repay a friend she owes only while she is currently holding at least that amount of cash (the cash she holds can never become negative). Because she may not have enough cash when she first reaches a friend she owes, she may have to walk past that friend, collect more money farther down the line, and come back to repay later.

Bessie starts at the barn (position $0$) and must finish at the far end of the line (position $N$). What is the minimum total distance she must travel to settle every account?

• Line 1: A single integer $N$.
• Lines 2 to $N+1$: Line $i+1$ contains a single integer $D_i$.

• Line 1: A single integer — the minimum total distance Bessie must travel to collect from and repay every friend.

In the sample, the five friends stand at positions $1$ to $5$ with values $100, -200, 250, -200, 200$.

• From the barn Bessie walks right and collects $100$ from friend $1$ (she now holds $100$).
• Friend $2$ is owed $200$, but Bessie holds only $100$, so she walks past and continues to friend $3$, collecting $250$ (she now holds $350$).
• She walks back to friend $2$ and repays $200$ (she now holds $150$).
• She walks right again to friend $5$, passing friend $4$ (owed $200$, but she holds only $150$) and collecting $200$ from friend $5$ (she now holds $350$).
• She walks back to friend $4$ and repays $200$ (she now holds $150$), then returns to the end of the line, where her journey ends.

The distances are $3 + 1 + 3 + 1 + 1 = 9$.