Wesley's Anger Contest 6 Problem 3 - Difference Sorting

View as PDF

Submit solution

Points: 10 (partial)
Time limit: 2.0s
Java 5.0s
Memory limit: 256M

Problem types

Wesley got an array of NN elements (a_1, a_2, \dots, a_Na_1, a_2, \dots, a_N) for Christmas, and is eager to sort it. Bored, Wesley decided to make it harder on himself by only allowing himself to swap two elements if the absolute difference between them is less than or equal to KK. Note that the elements can be anywhere; as long as their absolute difference is less than or equal to KK, Wesley can swap them.

Unfortunately, Wesley quickly realized that it might not be possible to sort the array. He then wonders: what is the minimum value of KK required to be able to sort the array?

For this problem, Python users are recommended to use PyPy over CPython.


For this problem, you will be required to pass all the samples in order to receive points. In addition, you must pass all previous subtasks to earn points for a specific subtask.

For all subtasks:

1 \le N \le 200\,0001 \le N \le 200\,000
1 \le a_i \le 10^{18}1 \le a_i \le 10^{18} for all 1 \le i \le N1 \le i \le N

Subtask 1 [18%]

1 \le N \le 2\,0001 \le N \le 2\,000
1 \le a_i \le 2\,0001 \le a_i \le 2\,000 for all 1 \le i \le N1 \le i \le N

Subtask 2 [82%]

No additional constraints.

Input Specification

The first line will contain NN, the number of the elements in the array.

The next line will contain NN integers a_1, a_2, \dots, a_Na_1, a_2, \dots, a_N, the array.

Output Specification

This problem is graded with an identical checker. This includes whitespace characters. Ensure that every line of output is terminated with a \n character and that there are no trailing spaces.

Output the minimum value of KK required to be able to sort the array. If the elements are already sorted you should output 0.

Sample Input

1 4 4 2 7 14 12 10

Sample Output


Sample Explanation

If we swap the second and fourth element, we obtain:

1 2 4 4 7 14 12 10

Now we can swap 1414 with 1212:

1 2 4 4 7 12 14 10

1212 with 1010:

1 2 4 4 7 10 14 12

And finally, 1212 with 1414:

1 2 4 4 7 10 12 14

It can be proven that this is the smallest possible KK.


There are no comments at the moment.