I. PermutationForces
data structures; greedy
You have a permutation \(p\) of integers from \(1\) to \(n\).You have a strength of \(s\) and will perform the following operation some times: Choose an index \(i\) such that \(1 \leq i \leq |p|\) and \(|i-p_i| \leq s\). For all \(j\) such that \(1 \leq j \leq |p|\) and \(p_i<p_j\), update \(p_j\) to \(p_j-1\). Delete the \(i\)-th element from \(p\). Formally, update \(p\) to \([p_1,\ldots,p_{i-1},p_{i+1},\ldots,p_n]\). It can be shown that no matter what \(i\) you have chosen, \(p\) will be a permutation of integers from \(1\) to \(|p|\) after all operations.You want to be able to transform \(p\) into the empty permutation. Find the minimum strength \(s\) that will allow you to do so.
The first line of input contains a single integer \(n\) (\(1 \leq n \leq 5 \cdot 10^5\)) — the length of the permutation \(p\).The second line of input conatains \(n\) integers \(p_1, p_2, \ldots, p_n\) (\(1 \leq p_i \leq n\)) — the elements of the permutation \(p\).It is guaranteed that all elements in \(p\) are distinct.
Print the minimum strength \(s\) required.
In the first test case, the minimum \(s\) required is \(1\).Here is how we can transform \(p\) into the empty permutation with \(s=1\): In the first move, you can only choose \(i=2\) as choosing any other value of \(i\) will result in \(|i-p_i| \leq s\) being false. With \(i=2\), \(p\) will be changed to \([2,1]\). In the second move, you choose \(i=1\), then \(p\) will be changed to \([1]\). In the third move, you choose \(i=1\), then \(p\) will be changed to \([~]\). It can be shown that with \(s=0\), it is impossible to transform \(p\) into the empty permutation.