Debt Settlement Route Optimization

Bessie has N friends with whom she has debt relationships. Each friend i (1 ≤ i ≤ N) is located at i meters from the barn. Friend i either owes Bessie D₍ᵢ₎ dollars (if D₍ᵢ₎ > 0) or Bessie owes friend i (if D₍ᵢ₎ < 0). Although Bessie starts at position 0 with no money, the total amount owed to her is greater than the amount she owes. On settlement day, as she walks along the line she may instantly collect the full amount from any friend that owes her money and, whenever she has enough money, repay the full debt to a friend she owes. She is allowed to backtrack along the line to settle any earlier unpaid debts and must finish her journey at the position of the last friend (i.e. at N meters).

The optimal strategy is as follows. Define the prefix sum [ f(i) = D₁ + D₂ + \cdots + D_{i}, \quad 0 \le i \le N, \quad f(0)=0. ] When f(i) drops below zero, it means that up to that point Bessie does not have enough money to pay all the debts encountered. In an optimal route, she delays paying until she collects enough money (i.e. until the prefix sum becomes nonnegative). At that moment she backtracks to the leftmost position where the negative interval began and then returns to resume her forward journey. If a contiguous negative interval starts at position s (the first index i for which f(i) < 0) and ends at position e (the first index after s with f(e) ≥ 0), then the extra distance traveled is [ 2\times(e - s), ] accounting for both the backward and forward segments. Summing all such negative intervals and adding the base distance (N) gives the minimum total distance:

[ \text{Distance} = N + \sum_{\text{each negative interval}} 2\times(e-s). ]

Your task is to compute this minimum distance.

inputFormat

The first line contains an integer N (1 ≤ N ≤ 100,000), the number of friends. The second line contains N nonzero integers D₁, D₂, …, Dₙ (|D₍ᵢ₎| ≤ 1000), where a positive D₍ᵢ₎ means friend i owes Bessie money, and a negative D₍ᵢ₎ means Bessie owes friend i.

outputFormat

Output a single integer representing the minimum total distance Bessie must travel to settle all transactions.

sample

3
-1 3 -1

5