CF1672I PermutationForces

你有一个由 $1$ 到 $n$ 的整数构成的排列 $p$。 你拥有一个强度 $s$，并且你将多次执行以下操作： - 选择一个下标 $i$，满足 $1 \leq i \leq |p|$ 且 $|i-p_i| \leq s$。 - 对所有满足 $1 \leq j \leq |p|$ 且 $p_i < p_j$ 的 $j$，将 $p_j$ 更新为 $p_j-1$。 - 删除排列中的第 $i$ 个元素。形式化地，将 $p$ 更新为 $[p_1,\ldots,p_{i-1},p_{i+1},\ldots,p_n]$。 可以证明，无论你选择了哪个 $i$，在所有操作结束后，$p$ 都会是一个从 $1$ 到 $|p|$ 的排列。 你希望能够将 $p$ 变为空排列。请你求出使其成为可能所需的最小强度 $s$。

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

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

在第一个测试用例中，所需的最小 $s$ 是 $1$。 以下是当 $s=1$ 时将 $p$ 变为空排列的操作过程： - 第一步，你只能选择 $i=2$，因为选择其他 $i$ 时 $|i-p_i| \leq s$ 不成立。此时 $p$ 变为 $[2,1]$。 - 第二步，你选择 $i=1$，此时 $p$ 变为 $[1]$。 - 第三步，你选择 $i=1$，此时 $p$ 变为 $[~]$。 可以证明，当 $s=0$ 时，不可能将 $p$ 变为空排列。 由 ChatGPT 4.1 翻译