P17136 [KOI 2026 #1] 数列排序

给定一个长度为 $N$ 的数列 $A = [A_1, A_2, \ldots, A_N]$。你可以任意进行若干次下述操作，操作次数可以为 $0$： 1. 选定一个正整数 $x$。 2. 从数列 $A$ 中提取所有值不大于 $x$ 的元素，并保持这些元素在原数列中的相对顺序不变，由此构成子序列 $B$。 3. 从数列 $A$ 中提取所有值大于 $x$ 的元素，并保持这些元素在原数列中的相对顺序不变，由此构成子序列 $C$。 4. 将原数列 $A$ 替换为依次拼接 $B$ 和 $C$ 得到的数列，即 $B+C$。 请编写一个程序，计算至少需要进行多少次操作，才能将数列 $A$ 按非递减顺序排列，即满足 $A_1 \le A_2 \le \cdots \le A_N$。 可以证明，对于所有满足限制条件的输入，都一定能够通过上述操作将给定数列按非递减顺序排列。

第一行输入一个整数 $N$。 第二行输入 $N$ 个整数 $A_1,A_2,\ldots,A_N$，整数之间以空格分隔。

第一行输出一个整数，表示将数列 $A$ 按非递减顺序排列所需的最少操作次数。

### 样例说明 1 可以按照如下方式，通过 $1$ 次操作将数列 $A$ 按非递减顺序排列。 1. 令 $x=2$。保持原有相对顺序，提取所有值不大于 $x=2$ 的元素，可得 $B:=[1,2]$。保持原有相对顺序，提取所有值大于 $x=2$ 的元素，可得 $C:=[3,4,5,6]$。因此，数列 $A$ 被替换为 $B+C=[1,2,3,4,5,6]$。 ### 样例说明 2 可以按照如下方式，通过 $2$ 次操作将数列 $A$ 按非递减顺序排列。 1. 令 $x=3$。保持原有相对顺序，提取所有值不大于 $x=3$ 的元素，可得 $B:=[1,1,1]$。保持原有相对顺序，提取所有值大于 $x=3$ 的元素，可得 $C:=[5,9,9,5,5,9]$。因此，数列 $A$ 被替换为 $B+C=[1,1,1,5,9,9,5,5,9]$。 2. 令 $x=7$。保持原有相对顺序，提取所有值不大于 $x=7$ 的元素，可得 $B:=[1,1,1,5,5,5]$。保持原有相对顺序，提取所有值大于 $x=7$ 的元素，可得 $C:=[9,9,9]$。因此，数列 $A$ 被替换为 $B+C=[1,1,1,5,5,5,9,9,9]$。 可以证明，无法通过少于 $2$ 次操作将数列 $A$ 按非递减顺序排列。 ### 限制条件 - 输入中给出的所有数均为整数。 - $1 \le N \le 300\,000$。 - 对于每个整数 $i$（$1 \le i \le N$），均有 $1 \le A_i \le N$。 ### 子任务 1. （$6$ 分）对于每个整数 $i$（$1 \le i \le N$），均有 $A_i \le 2$。 2. （$15$ 分）$N \le 15$。 3. （$23$ 分）$N \le 100$。 4. （$27$ 分）$N \le 750$。 5. （$33$ 分）对于任意整数 $i,j$（$1 \le i