The Cow Run

Interview

Time limit1sMemory limit128 MB

Summary

Cows sit at distinct positions on a line; John starts at 0, moves one unit per minute, and each cow costs one dollar per minute until reached. Minimize the sum of arrival times.

Level: Medium7 of 10
Topics: Dynamic programming, Greedy, Sorting, Intervals
Solved: No attempts yet

Problem

Farmer John forgot to repair a hole in the fence on his farm, and his $N$ cows ( $1 \le N \le 1000$ ) have escaped and gone on a rampage! For every minute a cow is outside the fence, it causes one dollar of damage. John must visit each cow to fit a halter that calms it and stops the damage.

Fortunately, the cows sit at distinct positions along a straight road outside the farm. John knows the position $P_i$ of each cow $i$ ( $-500000 \le P_i \le 500000$ , $P_i \ne 0$ ), measured relative to the gate (position 0) where John starts.

John moves one unit of distance per minute and can fit a halter instantly. Choose the order in which John visits the cows so as to minimize the total damage cost, and output that minimum total damage cost.

Input

Line 1: the number of cows, $N$ .
Lines 2 to $N+1$ : line $i+1$ contains the integer $P_i$ .

Output

Line 1: the minimum total damage cost.

Hint

Every cow accumulates one dollar of damage each minute until John fits its halter. Hence a cow's damage cost equals the time at which John reaches it (the total distance traveled from the gate so far), and the overall cost equals the sum of every cow's arrival time. Because John is always at one of the two ends of the block of cows he has already visited, the set of visited cows always forms a contiguous interval that contains position 0.

Examples4

Example 1
Input
```
4
-2
-12
3
7
```
Expected output
```
50
```
Example 2
Input
```
1
5
```
Expected output
```
5
```
Example 3
Input
```
1
-7
```
Expected output
```
7
```
Example 4
Input
```
2
3
10
```
Expected output
```
13
```