您有一个从 $$$1$$$ 到 $$$n$$$ 的整数排列 $$$p$$$。
你的实力为$$$s$$$,有时会执行以下操作:
- 选择一个索引 $$$i$$$ 使得 $$$1 \leq i \leq |p|$$$ 和 $$$|i-p_i| \leq s$$$。
- 对于所有 $$$j$$$,使得 $$$1 \leq j \leq |p|$$$ 和 $$$p_i<p_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$$$。
输入
输入的第一行包含一个整数 $$$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$$$。
示例
输入 #1
3 3 2 1
输出 #1
1
输入 #2
1 1
输出 #2
0
输入 #3
10 1 8 4 3 7 10 6 5 9 2
输出 #3
1
注意
在第一个测试用例中,所需的最低 $$$s$$$ 为 $$$1$$$。
以下是我们如何将 $$$p$$$ 转换为 $$$s=1$$$ 的空排列:
- 在第一步中,您只能选择 $$$i=2$$$,因为选择 $$$i$$$ 的任何其他值将导致 $$$|i-p_i| \leq s$$$ 为假。当 $$$i=2$$$ 时,$$$p$$$ 将更改为 $$$[2,1]$$$。
- 在第二步中,您选择$$$i=1$$$,则$$$p$$$将更改为$$$[1]$$$。
- 在第三步中,您选择$$$i=1$$$,则$$$p$$$将更改为$$$[~]$$$。
可以证明,$$$s=0$$$ 时,不可能将 $$$p$$$ 变换为空排列。