Farmer John olvidó reparar un agujero en la cerca; sus $N$ vacas $(1 \le N \le 1,000)$ escaparon y causan estragos. Cada minuto fuera de la cerca, una vaca causa un dólar de daños. FJ debe visitar a cada una y ponerle un cabestro para calmarla y detener los daños.
Por suerte, están en posiciones distintas sobre una línea recta de un camino fuera de la granja. FJ conoce la posición $P_i$ de cada vaca $i$ $(-500,000 \le P_i \le 500,000, P_i \ne 0)$ respecto a la puerta (posición 0) donde empieza.
FJ avanza una unidad de distancia por minuto y coloca el cabestro instantáneamente. Determina el orden de visita que minimiza el coste total de daños y calcula ese coste mínimo.
Entrada
- Línea 1: el número de vacas $N$.
- Líneas $2\ldots N+1$: la línea $i+1$ contiene el entero $P_i$.
Salida
- Línea 1: el coste total mínimo de daños.
Ejemplos
Entrada 1
4 -2 -12 3 7
Salida 1
50
Nota
Cuatro vacas están en posiciones $-2$, $-12$, $3$ y $7$.
El orden óptimo es $-2,3,7,-12$. FJ llega a $-2$ en 2 minutos, causando esa vaca 2 dólares de daños.
Después va a $3$ (distancia 5), donde los daños acumulados de esa vaca son $2 + 5 = 7$ dólares.
Tarda 4 minutos más en llegar a $7$, con $7 + 4 = 11$ dólares de daños por esa vaca.
Finalmente tarda 19 minutos en ir a $-12$, con un coste de $11 + 19 = 30$ dólares.
El total de daños es $2 + 7 + 11 + 30 = 50$ dólares.
Autor del problema: Chris Tzamos, 2006