Farmer John oublie de réparer un trou dans la clôture : ses $N$ vaches $(1 \le N \le 1,000)$ s’échappent et saccagent tout ! Chaque vache dehors cause un dollar de dégâts par minute. FJ doit lui mettre un licol pour la calmer et arrêter les dégâts.

Les vaches occupent des positions distinctes sur une route droite hors de la ferme. FJ connaît la position $P_i$ de chaque vache $i$ $(-500,000 \le P_i \le 500,000, P_i \ne 0)$ par rapport au portail (position $0$), son départ.

FJ avance d’une unité par minute et met un licol instantanément. Déterminez l’ordre minimisant les dégâts totaux et calculez ce minimum.

Entrée

• Ligne $1$ : nombre de vaches $N$.

• Lignes $2..N+1$ : la ligne $i+1$ contient l’entier $P_i$.

Sortie

• Ligne $1$ : dégâts totaux minimaux.

Exemples

Entrée 1

4
-2
-12
3
7

Sortie 1

50

Remarque

Quatre vaches en $-2$, $-12$, $3$, $7$.

Ordre optimal : $-2$, $3$, $7$, $-12$. FJ arrive en $-2$ après $2$ minutes, soit $2$ dollars pour cette vache.

Il va en $3$ (distance $5$) : dégâts de cette vache $2 + 5 = 7$ dollars.

Encore $4$ minutes pour $7$ : $7 + 4 = 11$ dollars pour cette vache.

Enfin $19$ minutes vers $-12$ : $11 + 19 = 30$ dollars.

Le total vaut $2 + 7 + 11 + 30 = 50$ dollars.

Auteur du problème : Chris Tzamos, 2006