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 N elements (a_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 K. Note that the elements can be anywhere; as long as their absolute difference is less than or equal to K, 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 K 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\,000
1 \le a_i \le 10^{18} for all 1 \le i \le N

Subtask 1 [18%]

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

Subtask 2 [82%]

No additional constraints.

Input Specification

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

The next line will contain N integers a_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 K 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 14 with 12:

1 2 4 4 7 12 14 10

12 with 10:

1 2 4 4 7 10 14 12

And finally, 12 with 14:

1 2 4 4 7 10 12 14

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


There are no comments at the moment.