«Não seja devedor nem credor.» Como Bessie queria ter seguido! Emprestou ou tomou emprestado de cada um de $N$ amigos, $(1 \le N \le 100,000)$, numerados $1,\ldots,N$.

Chega o dia do acerto. Devem-lhe mais do que ela deve aos outros. As vacas estão numa linha, a vaca $i$ a $i$ metros do celeiro. Ela percorrerá cobrando e pagando.

Pode pedir a qualquer devedora que pague. Quando tiver dinheiro suficiente para parte ou todas as dívidas, pode pagar com o recém-recebido. A vaca $i$ lhe deve $D_{i}$, $(-1,000 \le D_{i} \le 1,000; D_{i} \ne 0)$. Negativo significa que Bessie deve à vaca, o inverso.

Começa no celeiro, posição 0. Qual a distância mínima para cobrar tudo e pagar tudo? Deve acabar no fim da fila.

Entrada

• Linha 1: inteiro $N$.
• Linhas $2,\ldots,N+1$: a linha $i+1$ contém inteiro $D_{i}$.

Saída

• Linha 1: um inteiro, distância total em metros para cobrar ou pagar cada vaca.

Exemplos

Entrada 1

5
100
-200
250
-200
200

Saída 1

9

Nota

Três vacas devem a Bessie; ela deve a duas. Acaba com 150 de dinheiro.

      100  -200  250 -200  200
 |     |     |    |    |    |
 ***>**+**>*****>**+
                   *            < Bessie tem 350
             -**<***
             *                  < Bessie tem 150
             ***>****>****>**+
                             *  < Bessie tem 350
                       -**<***
                       *     
                       ***>***  < Bessie termina com 150*

À esquerda: celeiro.

Autor do problema: Jarrah Lacko, 2009