OCD Returns!

Limits 1s, 512 MB

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

Let's define $S$ 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 $S$ is too high. He wants $S$ 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 $i$ -th number should be at one of the three possible positions: $i - 1$ , $i$ , or $i+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 $S$ ?

Input

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

Output

Print the lowest value of $S$ .

Sample

Input Output

Input	Output
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 = \|1-2\| + \|2-3\| + \|3-4\| + \|4-5\| = 4$ (which is the minimum possible value of $S$ ).

5
2 1 4 3 5

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 = |1-2| + |2-3| + |3-4| + |4-5| = 4$ (which is the minimum possible value of $S$ ).