问题描述

有 $N$ 张卡片，每张卡片上都写着一个数字。下面对这叠卡片进行以下操作：

• 从叠中抽取一张卡片，然后插入到任意位置。

请计算为了将这叠卡片从上到下按升序排列所需的最小操作次数。

输入

输入将从标准输入中获取，格式如下：

$N$

$c_1$

$c_2$

...

$c_N$

• 第一行包含一个整数 $N(1≦N≦3 \times 10^4)$，表示卡片的数量。
• 接下来的 $N$ 行，描述了初始堆叠的状态。
  • 每行包含一个整数 $c_i$，表示第 $i$ 张卡片的值，满足 $1≦c_i≦N$。
  • $c_1$ 表示位于堆叠顶部的卡片，$c_N$ 表示位于堆叠底部的卡片。
  • 如果 $i \neq j$，$c_i \neq c_j$。也就是说，$N$ 张卡片上的数字都不相同。

输出

请计算为了将这叠卡片从上到下按升序排列所需的最小操作次数。

输出末尾必须换行。

部分点

本问题包含三个数据集，每个数据集都有特定的部分分数。

• 对于满足 $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