Farmer John esqueceu de consertar um buraco na cerca; suas $N$ vacas $(1 \le N \le 1,000)$ escaparam e causam estragos! A cada minuto fora da cerca, uma vaca causa um dólar de danos. FJ precisa visitar cada uma e pôr um cabresto que a acalme e pare os danos.
Felizmente estão em posições distintas numa linha reta de uma estrada fora da fazenda. FJ conhece a posição $P_i$ de cada vaca $i$ $(-500,000 \le P_i \le 500,000, P_i \ne 0)$ em relação ao portão (posição 0) onde começa.
FJ anda uma unidade de distância por minuto e põe o cabresto instantaneamente. Determine uma ordem de visita que minimize o custo total dos danos e calcule esse custo mínimo.
Entrada
- Linha 1: o número de vacas $N$.
- Linhas $2\ldots N+1$: a linha $i+1$ contém o inteiro $P_i$.
Saída
- Linha 1: o custo total mínimo dos danos.
Exemplos
Entrada 1
4 -2 -12 3 7
Saída 1
50
Nota
Quatro vacas estão nas posições $-2$, $-12$, $3$ e $7$.
A ordem ótima é $-2,3,7,-12$. FJ chega a $-2$ em 2 minutos, com 2 dólares de danos dessa vaca.
Depois vai a $3$ (distância 5), onde os danos acumulados dessa vaca são $2 + 5 = 7$ dólares.
Leva mais 4 minutos para chegar a $7$, com $7 + 4 = 11$ dólares de danos dessa vaca.
Por fim, leva 19 minutos para ir a $-12$, com custo de $11 + 19 = 30$ dólares.
O total de danos é $2 + 7 + 11 + 30 = 50$ dólares.
Autor do problema: Chris Tzamos, 2006