У вас есть перестановка \(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\), которая позволит вам это сделать.
Выходные данные
Выведите минимальную необходимую силу \(s\).
Примечание
В первом примере минимальное требуемое значение \(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\) в пустую перестановку.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
3 2 1
|
1
|
|
2
|
1
1
|
0
|
|
3
|
10
1 8 4 3 7 10 6 5 9 2
|
1
|