問題文
写有数字的卡片 有 N 件。您可以对这叠牌(牌组)执行以下操作。
- 牌组中的牌 1 取出纸张并将其插入任意位置。
求出将牌从上到下按升序排序所需的最少操作次数。
入力
N c_1 c_2 : c_N
- 1 行是一个整数,表示卡片的数量。 给出了 N(1≦N≦3 \times 10^4) 。 来自行
-
2 牌组的初始状态在 N 行中给出。
-
c_i 从甲板顶部
一个整数,表示 i 卡,1≦c_i≦N 很满意。
- c_1 是这副牌的顶牌,c_N 表示牌组底部的牌。
- i \neq j 如果 c_i \neq c_j 。换句话说,N 所有卡片上都写有不同的数字。
-
c_i 从甲板顶部
一个整数,表示 i 卡,1≦c_i≦N 很满意。
出力
求出将牌从上到下按升序排序所需的最少操作次数。
同时,输出末尾要加换行。部分点
这个问题有 3 有两个数据集,每个数据集都设置了部分点。 如果您对满足
- N(1≦N≦16) 的所有数据集回答正确, 如果您对除上述数据集之外的所有满足10 分被给予。
- N(1≦N≦1,000) 的数据集回答正确, 40 分被给予。
- 如果所有数据集都回答正确, 删除100 分被给予。
入力例 1
6 1 3 5 2 4 6
出力例 1
2
- 2 删除 1 和 将其放在 3 之间。
- 5 删除 4 和 将其放在 6 之间。
入力例 2
5 5 4 3 2 1
出力例 2
4
入力例 3
7 1 2 3 4 5 6 7
出力例 3
0