Problem Description

Farmer John has forgotten to repair a hole in the fence on his farm, and his $N$ cows ($1 \le N \le 1,000$) have escaped and gone on a rampage! Each minute a cow is outside the fence, she causes one dollar worth of damage. FJ must visit each cow to install a halter that will calm the cow and stop the damage.

Fortunately, the cows are positioned at distinct locations along a straight line on a road outside the farm. FJ knows the location $P_i$ of each cow $i$ ($-500,000 \le P_i \le 500,000$, $P_i \ne 0$) relative to the gate (position $0$) where FJ starts.

FJ moves at one unit of distance per minute and can install a halter instantly. Please determine the order that FJ should visit the cows so he can minimize the total cost of the damage; you should compute the minimum total damage cost in this case.

Input Format

• Line $1$: The number of cows, $N$.
• Lines $2 \dots N+1$: Line $i+1$ contains the integer $P_i$.

Output Format

• Line $1$: The minimum total cost of the damage.

4 
-2 
-12 
3 
7 

50 

Hint

Four cows placed in positions: $-2$, $-12$, $3$, and $7$.

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

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

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.