Farmer John zapomniał naprawić dziurę w płocie; jego $N$ krów $(1 \le N \le 1,000)$ uciekło i szaleje! Każda minuta poza płotem to dolar szkód od każdej krowy. FJ musi odwiedzić każdą i założyć kantar, który ją uspokoi i zatrzyma szkody.

Na szczęście krowy stoją w różnych punktach prostej na drodze poza farmą. FJ zna pozycję $P_i$ każdej krowy $i$ $(-500,000 \le P_i \le 500,000, P_i \ne 0)$ względem bramy (pozycja 0), gdzie zaczyna.

FJ porusza się o jednostkę odległości na minutę i zakłada kantar natychmiast. Wyznacz kolejność odwiedzin minimalizującą łączny koszt szkód i oblicz ten minimalny koszt.

Wejście

• Wiersz 1: liczba krów $N$.
• Wiersze $2\ldots N+1$: wiersz $i+1$ zawiera liczbę całkowitą $P_i$.

Wyjście

• Wiersz 1: minimalny łączny koszt szkód.

Przykład

Wejście 1

4
-2
-12
3
7

Wyjście 1

50

Uwagi

Cztery krowy stoją na pozycjach $-2$, $-12$, $3$ i $7$.

Optymalna kolejność to $-2,3,7,-12$. FJ dociera do $-2$ w 2 minuty, więc szkody tej krowy to 2 dolary.

Potem idzie do $3$ (dystans 5), gdzie skumulowane szkody tej krowy to $2 + 5 = 7$ dolarów.

Potrzebuje kolejnych 4 minut do $7$, ze szkodami $7 + 4 = 11$ dolarów od tej krowy.

Na końcu potrzebuje 19 minut do $-12$, z kosztem $11 + 19 = 30$ dolarów.

Łączne szkody to $2 + 7 + 11 + 30 = 50$ dolarów.

Autor zadania: Chris Tzamos, 2006