«Ne sois ni emprunteur ni prêteur.» Bessie regrette de ne pas avoir suivi ce conseil ! Elle a emprunté ou prêté à chacun de $N$ amis, $(1 \le N \le 100,000)$, numérotés $1,\ldots,N$.

Le jour du remboursement arrive. On lui doit plus qu'elle ne doit aux autres. Les vaches sont alignées, la vache $i$ à $i$ mètres de la grange. Elle parcourt la file, recouvrant ses créances et remboursant ses dettes.

Elle peut réclamer son argent à toute vache qui lui doit. Dès qu'elle en a assez pour une partie ou toutes ses dettes, elle peut verser l'argent récemment collecté aux créancières. La vache $i$ lui doit $D_{i}$, $(-1,000 \le D_{i} \le 1,000; D_{i} \ne 0)$. Un montant négatif signifie que Bessie doit à cette vache, et non l'inverse.

Elle part de la grange, position 0. Quelle distance minimale pour tout collecter et tout rembourser ? Elle doit terminer au bout de la file.

Entrée

• Ligne 1 : entier $N$.
• Lignes $2,\ldots,N+1$ : ligne $i+1$, un entier $D_{i}$.

Sortie

• Ligne 1 : un entier, la distance totale en mètres nécessaire pour régler avec chaque vache.

Exemples

Entrée 1

5
100
-200
250
-200
200

Sortie 1

9

Remarque

Trois vaches doivent à Bessie ; elle doit à deux. Elle finit avec 150 d'argent.

      100  -200  250 -200  200
 |     |     |    |    |    |
 ***>**+**>*****>**+
                   *            < Bessie a 350
             -**<***
             *                  < Bessie a 150
             ***>****>****>**+
                             *  < Bessie a 350
                       -**<***
                       *     
                       ***>***  < Bessie finit avec 150*

À gauche : grange.

Auteur du problème : Jarrah Lacko, 2009