Farmer John ha dimenticato di riparare un buco nella recinzione; le sue $N$ mucche $(1 \le N \le 1,000)$ sono fuggite e fanno danni! Ogni minuto fuori dalla recinzione una mucca causa un dollaro di danni. FJ deve visitare ciascuna e metterle una cavezza per calmarla e fermare i danni.
Fortunatamente sono in posizioni distinte lungo una retta su una strada fuori dalla fattoria. FJ conosce la posizione $P_i$ di ogni mucca $i$ $(-500,000 \le P_i \le 500,000, P_i \ne 0)$ rispetto al cancello (posizione 0) da cui parte.
FJ si muove di un'unità di distanza al minuto e mette una cavezza istantaneamente. Determina l'ordine di visita che minimizza il costo totale dei danni e calcola tale costo minimo.
Input
- Riga 1: il numero di mucche $N$.
- Righe $2\ldots N+1$: la riga $i+1$ contiene l'intero $P_i$.
Output
- Riga 1: il costo totale minimo dei danni.
Esempi
Input 1
4 -2 -12 3 7
Output 1
50
Nota
Quattro mucche sono in posizione $-2$, $-12$, $3$ e $7$.
L'ordine ottimo è $-2,3,7,-12$. FJ arriva in $-2$ in 2 minuti, per 2 dollari di danni di quella mucca.
Poi va in $3$ (distanza 5), dove i danni accumulati di quella mucca sono $2 + 5 = 7$ dollari.
Impiega altri 4 minuti per arrivare in $7$, con $7 + 4 = 11$ dollari di danni di quella mucca.
Infine impiega 19 minuti per andare in $-12$, con costo di $11 + 19 = 30$ dollari.
Il danno totale è $2 + 7 + 11 + 30 = 50$ dollari.
Autore del problema: Chris Tzamos, 2006