Farmer John hat ein Loch im Hofzaun nicht repariert; seine $N$ Kühe $(1 \le N \le 1,000)$ sind entkommen und wüten! Jede Kuh verursacht pro Minute außerhalb des Zauns einen Dollar Schaden. FJ muss jede besuchen und ein Halfter anlegen, das sie beruhigt und den Schaden beendet.

Zum Glück stehen sie an verschiedenen Stellen auf einer Geraden entlang einer Straße außerhalb des Hofs. FJ kennt die Position $P_i$ jeder Kuh $i$ $(-500,000 \le P_i \le 500,000, P_i \ne 0)$ relativ zum Tor (Position 0), wo er startet.

FJ bewegt sich eine Entfernungseinheit pro Minute und legt ein Halfter sofort an. Bestimme die Besuchsreihenfolge mit minimalen Gesamtschäden und berechne diese minimalen Kosten.

Eingabe

• Zeile 1: die Kuhzahl $N$.
• Zeilen $2\ldots N+1$: Zeile $i+1$ enthält die ganze Zahl $P_i$.

Ausgabe

• Zeile 1: die minimalen Gesamtschadenskosten.

Beispiele

Eingabe 1

4
-2
-12
3
7

Ausgabe 1

50

Hinweis

Vier Kühe stehen bei $-2$, $-12$, $3$ und $7$.

Die optimale Reihenfolge ist $-2,3,7,-12$. FJ erreicht $-2$ in 2 Minuten; diese Kuh verursacht 2 Dollar Schaden.

Dann geht er zu $3$ (Entfernung 5), wo der aufgelaufene Schaden dieser Kuh $2 + 5 = 7$ Dollar beträgt.

Weitere 4 Minuten braucht er zu $7$, mit $7 + 4 = 11$ Dollar Schaden dieser Kuh.

Schließlich braucht er 19 Minuten zu $-12$, mit Kosten von $11 + 19 = 30$ Dollar.

Der Gesamtschaden ist $2 + 7 + 11 + 30 = 50$ Dollar.

Aufgabenautor: Chris Tzamos, 2006