[Solution] PermutationForces solution codeforces

PermutationForces solution codeforces – 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}, \dots, p_{i - 1}, p_{i + 1}, \dots, 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.

Input

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}, \dots, 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.

Examples

input

Copy

3
3 2 1

output

Copy

input

Copy

1
1

output

Copy

input

Copy

10
1 8 4 3 7 10 6 5 9 2

output

Copy

PermutationForces solution codeforces

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.