Description

Farmer John forgot to repair a hole in his fence, and his $N$ cows ($1 \le N \le 1000$) escaped. Each minute a cow is outside the fence, she causes one dollar of damage. Farmer John must visit each cow to install a halter that calms the cow and stops the damage.

The cows are positioned at distinct locations along a straight road outside the farm. Farmer John knows the position $P_i$ of each cow $i$ (relative to the gate at position $0$ where he starts), with $-500000 \le P_i \le 500000$ and $P_i \ne 0$.

Farmer John moves at one unit of distance per minute, and installing a halter is instantaneous. Determine the order in which he should visit the cows to minimize the total damage, and compute the minimum total damage cost.

Input Format

• Line 1: An integer $N$, the number of cows.
• Lines $2..N+1$: Line $i+1$ contains an integer $P_i$.

Output Format

• Line 1: A single integer, the minimum total damage cost.

4 
-2 
-12 
3 
7 

50 

Hint

Four cows are at positions $-2$, $-12$, $3$, and $7$.

The optimal visit order is $-2$, $3$, $7$, $-12$. Farmer John arrives at position $-2$ in $2$ minutes, causing $2$ dollars of damage for that cow.

He then travels to position $3$ (distance $5$), where the cumulative damage for that cow is $2 + 5 = 7$ dollars.

He spends $4$ more minutes to get to $7$ at a cost of $7 + 4 = 11$ dollars for that cow.

Finally, he spends $19$ minutes to go to $-12$ with a cost of $11 + 19 = 30$ dollars.

The total damage is $2 + 7 + 11 + 30 = 50$ dollars.

Translated by ChatGPT 5