Recently IMO 2015 has ended. Problem 6 was the hardest one and solved by only 11 contestants, but for competitive programmers this task wasn't that hard. If you are interested in it, I think it's worth trying even if you haven't solved any IMO problems.

The problem statement is here.

I wrote some hints in white characters.

Hint 1: How is it related to competitive programming?

Hint 2: Doesn't it look like bitmask DP?

Hint 3: Run the following program.

mask = 0;

for(i=1;;i++){

mask» = 1;

mask| = (1«(a_i - 1)); // here the newly set bit must be 0 before this operation

}

Hint 4: The number of '1' bits in mask is non-decreasing while the program is running.

So, the number of '1' bits will be constant at some moment: call it b.

Then, the sum of (a_j - b) is the difference of sum of positions of set bits in mask when i = m and i = n.