問題文
都有不同的高度 N 积木 它们排列在 1 列中。彼此相邻 如果您多次重新排列 2 构建块,使它们从最高的构建块开始并向左下方和右下方移动,请找到所需的最小替换次数。也就是排序之后 i 构建块的高度为 Ai 最高构建块的位置是 T 当 求排序满足
- A1 < A2 < ... < AT > ... > AN-1 > AN
入力
输入是按以下格式从标准输入给出的。
N B1 B2 ... BN
- 1 行中积木的数量 N (1≦N≦10^5) 用空格分隔。
- 2 积木的高度显示在行中 Bi (1≦Bi≦N) 按首次列出的顺序给出。
- 然而,积木的高度都不同。也就是说,Bi≠Bj (i≠j) 成立。
出力
输出排序所需的最小交换次数。在输出末尾添加换行符。
部分点
这个问题有 2 有两个数据集,每个数据集都设置了部分点。 满足
- N≦100 的数据集 如果您回答正确 1 如果你回答正确的话, 30 点。
- 没有附加约束的数据集 如果您对 2 的回答正确,除了上述数据集之外, 70 点。
入力例1
4 2 4 1 3
出力例1
1
如下 按 1 次排序。 下面是按
入力例2
5 2 4 1 3 5
出力例2
3
3 次排序的示例。 调整
入力例3
6 1 2 4 3 5 6
出力例3
1