← 返回题目列表

AtCoder · arc031_3

C. 积木

中文机器翻译题面 查看原题

問題文

都有不同的高度 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