← 返回题目列表

AtCoder · abc006_4

D. 扑克牌插入排序

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

問題文

写有数字的卡片 有 N 件。您可以对这叠牌(牌组)执行以下操作。

  • 牌组中的牌 1 取出纸张并将其插入任意位置。

求出将牌从上到下按升序排序所需的最少操作次数。


入力

输入将以以下形式通过标准输入给出。
N
c_1
c_2
:
c_N
  1. 1 行是一个整数,表示卡片的数量。 给出了 N(1≦N≦3 \times 10^4) 。 来自行
  2. 2 牌组的初始状态在 N 行中给出。
    • c_i 从甲板顶部 一个整数,表示 i 卡,1≦c_i≦N 很满意。
      • c_1 是这副牌的顶牌,c_N 表示牌组底部的牌。
    • i \neq j 如果 c_i \neq c_j 。换句话说,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