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.

Constraints

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

8
1 4 4 2 7 14 12 10

Sample Output

2

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~.