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, 256 MB

This problem author has OCD (obsessive–compulsive disorder). One day his teacher gave him an array of N (1 ≤ N ≤ 105) elements. The absolute value of each element is less than 105.

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 position { i - 1, i, 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?


There will be only one test case per input file. The input file will start with a number N denoting the size of the array. On the next line there will be N numbers which are elements of the array. Each number of the array will be separated by a single space.


On a single line print the lowest value of S.


2 1 4 3 5

In the given sample test case,

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 minimum possible value of S)

  • himuhasib's Avatar


    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.