Farmer John nie naprawił dziury w płocie i $N$ krów $(1 \le N \le 1,000)$ uciekło i rozrabia! Każda poza płotem powoduje dolara szkody na minutę. FJ musi odwiedzić każdą i założyć kantar, uspokajając ją i zatrzymując szkody.

Stoją w różnych punktach prostej drogi poza farmą. FJ zna pozycję $P_i$ krowy $i$ $(-500,000 \le P_i \le 500,000, P_i \ne 0)$ względem bramy (pozycja $0$), gdzie zaczyna.

FJ idzie jednostkę na minutę i zakłada kantar natychmiast. Określ kolejność minimalizującą szkody i oblicz minimalną sumę.

Wejście

• Wiersz $1$: liczba krów $N$.

• Wiersze $2..N+1$: wiersz $i+1$ zawiera całkowite $P_i$.

Wyjście

• Wiersz $1$: minimalna suma szkód.

Przykład

Wejście 1

4
-2
-12
3
7

Wyjście 1

50

Uwagi

Cztery krowy w $-2$, $-12$, $3$, $7$.

Optymalnie $-2$, $3$, $7$, $-12$. W $-2$ jest po $2$ minutach: szkoda tej krowy $2$ dolary.

Potem do $3$ (odległość $5$): $2 + 5 = 7$ dolarów dla tej krowy.

Jeszcze $4$ minuty do $7$: $7 + 4 = 11$ dolarów.

Na koniec $19$ minut do $-12$: $11 + 19 = 30$ dolarów.

Suma $2 + 7 + 11 + 30 = 50$ dolarów.

Autor zadania: Chris Tzamos, 2006