题目描述

给定一个长度为 $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$ 按非递减顺序排列所需的最少操作次数。

6
3 4 5 1 2 6

1

9
1 5 9 9 5 1 1 5 9

2

提示

样例说明 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<j \le N$），均有 $A_i \ne A_j$。
6. （$46$ 分）无附加限制。

翻译由 ChatGPT-5.6 完成