Problem F: 数列排序

Memory Limit：128 MB Time Limit：1.000 S

Submit：8 Solved：4

一维数组

给定一个长度为 $N$ 的数列 $A = [A 1, A 2, \dots, A N]$ 。你可以任意进行若干次下述操作，操作次数可以为 $0$ ：

请编写一个程序，计算至少需要进行多少次操作，才能将数列 $A$ 按非递减顺序排列，即满足 $A 1 \leq A 2 \leq \dots \leq A N$ 。

可以证明，对于所有满足限制条件的输入，都一定能够通过上述操作将给定数列按非递减顺序排列。

第一行输入一个整数 $N$ 。

第二行输入 $N$ 个整数 $A 1, A 2, \dots, A N$ 整数之间以空格分隔。

第一行输出一个整数，表示将数列

A

按非递减顺序排列所需的最少操作次数。

6
3 4 5 1 2 6

9
1 5 9 9 5 1 1 5 9

可以按照如下方式，通过 $1$ 次操作将数列 $A$ 按非递减顺序排列。

令 $x = 2$ 。保持原有相对顺序，提取所有值不大于 $x = 2$ 的元素，可得 $B := [1, 2]$ 。保持原有相对顺序，提取所有值大于 $x = 2$ 的元素，可得 $C := [3, 4, 5, 6]$ 。因此，数列 $A$ 被替换为 $B + C = [1, 2, 3, 4, 5, 6]$ 。

可以按照如下方式，通过 $2$ 次操作将数列 $A$ 按非递减顺序排列。

令 $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]$ 。
令 $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$ 按非递减顺序排列。