I. PermutationForcestime limit per test5 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard outputYou 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.InputThe 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.OutputPrint the minimum strength s required.ExamplesInput
3
3 2 1
Output
1
Input
1
1
Output
0
Input
10
1 8 4 3 7 10 6 5 9 2
Output
1
NoteIn 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.
3
3 2 1

1 
['data structures', 'greedy', '*3000']