题目背景

试题来源：https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

有 $N$ 张卡片按左右一排排列。每张卡片上写有一个整数，第 $i$ 张卡片上写的整数是 $A_i$。（$1 \leq i \leq N$）

你可以从这 $N$ 张卡片中选择若干张卡片并将其移除。此时，剩下卡片的顺序保持不变。

例如，设 $N = 5$，$A = [3, 1, 4, 1, 5]$。如果你移除了第二张和第五张卡片，那么剩下卡片上的数字依次为 3、4、1。也就是说，剩下的卡片中从左数第 3 张卡片上的数字是 1。

移除若干张卡片后，如果剩下卡片中从左数第 $x$ 张卡片上写的数正好等于 $x$，那么我们称该卡片为“原位卡片”。如果所有剩下的卡片都是原位卡片，那么我们称卡片序列达到了“原位状态”。

例如，设 $N = 8$，$A = [6, 1, 2, 3, 2, 4, 5, 10]$。如果你移除了第一张、第五张和第八张卡片，那么剩下的卡片上的数依次为 1、2、3、4、5。在这种情况下，所有剩下的卡片都是原位卡片，因此卡片序列处于原位状态。

又如，若 $N = 6$，$A = [3, 4, 6, 10, 2, 5]$，为了达到原位状态，必须将所有卡片都移除，使得不剩下一张卡片。

请注意，如果将所有卡片都移除，总是可以达到原位状态。

请编写程序，计算为了使卡片序列达到原位状态，至少需要移除多少张卡片。

输入格式

第一行包含一个整数 $N$。

第二行包含 $N$ 个整数 $A_1, A_2, \ldots, A_N$，依次给出。

输出格式

输出一个整数，表示最少需要移除的卡片数。

1
1

0

8
6 1 2 3 2 4 5 10

3

6
3 4 6 10 2 5

6

提示

约束条件

• $1 \leq N \leq 250\,000$
• 对于所有的 $i$（$1 \leq i \leq N$），有 $1 \leq A_i \leq 250\,000$

子任务

1. （5 分）$N = 1$
2. （16 分）$N \leq 20$
3. （28 分）$N \leq 1\,500$
4. （51 分）无额外限制条件