Farmer John has forgotten to repair a hole in the fence on his farm, and his N cows (1 <= N <= 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 <= P_i <= 500,000, P_i != 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.

(This problem appeared identically as the Silver problem 3 and Gold problem 1 of the USACO 2013 March contest.)

Line 1: The number of cows, N.

Lines 2..N+1: Line i+1 contains the integer P_i.

The minimum total cost of the damage.

riseoj 작성

출처 올림피아드 > USACO > 2012-2013 > March > Silver