I. PermutationForces
ограничение по времени на тест
5 секунд
ограничение по памяти на тест
1024 мегабайта
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть перестановка $$$p$$$ целых чисел от $$$1$$$ до $$$n$$$.

У вас есть сила $$$s$$$ и вы будете выполнять следующую операцию несколько раз:

  • Выберите индекс $$$i$$$ такой, что $$$1 \leq i \leq |p|$$$ и $$$|i-p_i| \leq s$$$.
  • Для всех $$$j$$$ таких, что $$$1 \leq j \leq |p|$$$ и $$$p_i<p_j$$$, заменить $$$p_j$$$ на $$$p_j-1$$$.
  • Удалить $$$i$$$-й элемент из $$$p$$$. Формально, заменить $$$p$$$ на $$$[p_1,\ldots,p_{i-1},p_{i+1},\ldots,p_n]$$$.

Можно показать, что независимо от того, какое число $$$i$$$ вы выбрали, после всех операций $$$p$$$ будет перестановкой целых чисел от $$$1$$$ до $$$|p|$$$.

Вы хотите превратить $$$p$$$ в пустую перестановку. Найдите минимальную силу $$$s$$$, которая позволит вам это сделать.

Входные данные

Первая строка ввода содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 5 \cdot 10^5$$$)  — длину перестановки $$$p$$$.

Вторая строка ввода содержит $$$n$$$ целых чисел $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \leq p_i \leq n$$$)  — элементы перестановки $$$p$$$.

Гарантируется, что все элементы в $$$p$$$ различны.

Выходные данные

Выведите минимальную необходимую силу $$$s$$$.

Примеры
Входные данные
3
3 2 1
Выходные данные
1
Входные данные
1
1
Выходные данные
0
Входные данные
10
1 8 4 3 7 10 6 5 9 2
Выходные данные
1
Примечание

В первом примере минимальное требуемое значение $$$s$$$ равно $$$1$$$.

Вот как мы можем преобразовать $$$p$$$ в пустую перестановку с $$$s=1$$$:

  • В первую операцию можно выбрать только $$$i=2$$$, так как при любом другом значении $$$i$$$ условие $$$|i-p_i| \leq s$$$ не будет выполнено. При $$$i=2$$$, $$$p$$$ изменится на $$$[2,1]$$$.
  • Во вторую операцию, если выбрать $$$i=1$$$, то $$$p$$$ изменится на $$$[1]$$$.
  • В третью операциб, вы выбираете $$$i=1$$$, тогда $$$p$$$ будет изменено на $$$[~]$$$.

Можно показать, что при $$$s=0$$$ невозможно преобразовать $$$p$$$ в пустую перестановку.