P12696 [KOI 2022 Round 2] 原位卡片

试题来源：。中文翻译做了少量本土化修改。 按照[署名—非商业性使用—相同方式共享 4.0 协议国际版](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hans)进行授权。

有 $ 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 \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 分）无额外限制条件