OCD Returns!

himuhasib ProgKriya May'16
Limits 1s, 512 MB

This problem author has OCD (obsessive–compulsive disorder). One day his teacher gave him an array of NN elements.

Let's define SS as the sum of absolute difference of adjacent elements.

Guess what? He doesn't like the array so much. Because he found that the value of SS is too high. He wants SS to have a value as low as possible.

But again he has OCD. He doesn't want to move the elements of the array too much. He rearranges the array such that every element is either at it's own position, or at it's left position, or at it's right position. In other words, the ii-th number should be at one of the three possible positions: i1i - 1, ii, or i+1i+1. No two numbers should stay at the same position. And no position should be left blank.

Note that for the first element he can't move the element to left, and for the last element he can't move the element to right.

Now he asks you, after rearranging the numbers, what's the lowest value of SS?

Input

The input will start with the integer NN (1N1051 ≤ N ≤ 10^5) denoting the size of the array. On the next line there will be NN integers which are elements of the array. Each integer AiA_i (Ai<105|A_i| < 10^5) of the array will be separated by a single space.

Output

Print the lowest value of SS.

Sample

InputOutput
5
2 1 4 3 5
4

In the given sample test case, the first element moves to right, second element moves to left, third element moves to right, fourth element moves to left. So the new array will look like [1, 2, 3, 4, 5].

For this new array, S=12+23+34+45=4S = |1-2| + |2-3| + |3-4| + |4-5| = 4 (which is the minimum possible value of SS).


Submit

Login to submit.

Statistics

25% Solution Ratio
midnightbirdEarliest, May '16
Emrul.047263Fastest, 0.0s
Emrul.047263Lightest, 12 kB
Riaz_BSMRSTUShortest, 541B
Toph uses cookies. By continuing you agree to our Cookie Policy.