CF1672I.PermutationForces

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 \lt 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.

你有一个 $1$ 到 $n$ 的整数排列 $p$。

你拥有强度 $s$，并可执行以下操作若干次：

• 选择一个下标 $i$，满足 $1 \leq i \leq |p|$ 且 $|i-p_i| \leq s$；
• 对所有满足 $1 \leq j \leq |p|$ 且 $p_i \lt p_j$ 的 $j$，将 $p_j$ 更新为 $p_j-1$；
• 从 $p$ 中删除第 $i$ 个元素。形式化地，将 $p$ 更新为 $[p_1,\ldots,p_{i-1},p_{i+1},\ldots,p_n]$。

可以证明：无论你选择哪个 $i$，在所有操作完成后，$p$ 始终是 $1$ 到 $|p|$ 的一个排列。

你希望最终能将 $p$ 变为一个空排列。求实现该目标所需的最小强度 $s$。

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.

输入的第一行包含一个整数 $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$ 中所有元素互不相同。

Print the minimum strength $s$ required.

输出所需的最小强度 $s$。

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.

在第一个测试用例中，所需的最小 $s$ 为 $1$。

以下是当 $s=1$ 时，我们将 $p$ 变换为空排列的过程：

• 在第一步中，你只能选择 $i=2$，因为选择其他任意 $i$ 值都会导致 $|i-p_i| \leq s$ 不成立。当 $i=2$ 时，$p$ 将变为 $[2,1]$。
• 在第二步中，你选择 $i=1$，则 $p$ 将变为 $[1]$。
• 在第三步中，你选择 $i=1$，则 $p$ 将变为 $[~]$。

可以证明：当 $s=0$ 时，无法将 $p$ 变换为空排列。