Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

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 ith 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 ≤ 105) denoting the size of the array. On the next line there will be N integers which are elements of the array. Each integer Ai (|Ai| < 105) of the array will be separated by a single space.

Output

Print the lowest value of S.

Samples

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

Author
  • himuhasib's Avatar

    himuhasib

    Hasib is passionate about sport programming and artificial intelligence. He was an IOI participant through years 2013-2015. He qualified to ACM-ICPC World Finals 2016. He studies at North South University.
Discussion