Minimizing Damage from Escaped Cows

Farmer John forgot to repair a hole in his fence, and as a result, N cows have escaped and are causing damage! Each minute a cow is outside, it incurs $1 of damage. The cows are located at distinct positions along a straight road outside the farm. The location of cow i is given by P_i with the constraint \( -5 \times 10^5 \le P_i \le 5 \times 10^5 \) and \(P_i \neq 0\). Farmer John starts at position 0 (the gate) and moves at a rate of one unit per minute; when he reaches a cow, he can instantly install a halter to stop that cow from causing any further damage.

Every minute that passes, each cow that has not yet been halted continues to cause \($1\) damage. In other words, if Farmer John takes a route during which there are k cows still running free and he travels a distance of d, he will incur a cost of \( k \times d \). Your task is to determine the optimal route (i.e. the order in which to visit the cows) so that the total damage cost is minimized. The total cost is the sum over each segment of the journey, where each segment cost is equal to the remaining number of cows multiplied by the distance traveled in that segment.

Note: The problem requires you to compute the minimum total damage cost.

inputFormat

The first line of input contains a single integer \(N\) (\(1 \le N \le 1000\)), the number of cows. Each of the following \(N\) lines contains an integer \(P_i\) representing the location of the \(i\)th cow, where \( -5\times10^5 \le P_i \le 5\times10^5 \) and \(P_i \neq 0\).

outputFormat

Output a single integer representing the minimum total damage cost incurred by Farmer John if he visits the cows in an optimal order.

sample

3
-1
3
4

12