„Nie bądź pożyczkobiorcą ani pożyczkodawcą”. Bessie żałuje, że nie posłuchała! Brała lub dawała pożyczki każdemu z $N$ przyjaciół, $(1 \le N \le 100,000)$, oznaczonych $1,\ldots,N$.

Nastał dzień spłaty. Należy się jej więcej, niż sama jest winna innym. Krowy stoją w prostej linii, krowa $i$ w odległości $i$ metrów od stodoły. Bessie pójdzie wzdłuż, odbierając i spłacając pieniądze.

Może poprosić dowolną dłużniczkę o zwrot. Gdy ma dość na część lub wszystkie długi, może płacić właśnie odebranymi pieniędzmi. Krowa $i$ jest jej winna $D_{i}$, $(-1,000 \le D_{i} \le 1,000; D_{i} \ne 0)$. Ujemna wartość znaczy odwrotnie: Bessie jest winna krowie.

Zaczyna przy stodole, pozycji 0. Jaka minimalna droga, by odebrać wszystko i spłacić wszystko? Musi skończyć na końcu szeregu.

Wejście

• Wiersz 1: całkowite $N$.
• Wiersze $2,\ldots,N+1$: wiersz $i+1$ zawiera całkowite $D_{i}$.

Wyjście

• Wiersz 1: jedna liczba całkowita, łączna droga w metrach do rozliczenia z każdą krową.

Przykład

Wejście 1

5
100
-200
250
-200
200

Wyjście 1

9

Uwagi

Trzy krowy są winne Bessie, ona jest winna dwóm. Skończy ze 150 pieniędzy.

      100  -200  250 -200  200
 |     |     |    |    |    |
 ***>**+**>*****>**+
                   *            < Bessie ma 350
             -**<***
             *                  < Bessie ma 150
             ***>****>****>**+
                             *  < Bessie ma 350
                       -**<***
                       *     
                       ***>***  < Bessie kończy z 150*

Po lewej: stodoła.

Autor zadania: Jarrah Lacko, 2009