A16687. Locked Out
编程题
提高+/省选-
知识点
题目描述
什么样的数组才是好数组？你就是好数组！（c）
如果对于数组 $b$，不存在 $1 \leq i < j \leq |b|$ 满足 $b_j - b_i = 1$，那么这个数组被称为好数组。
现在给定一个整数数组 $a_1, a_2, \ldots, a_n$。你的任务是确定，最少需要删除多少个元素，使得该数组变成好数组。
如果对于数组 $b$，不存在 $1 \leq i < j \leq |b|$ 满足 $b_j - b_i = 1$，那么这个数组被称为好数组。
现在给定一个整数数组 $a_1, a_2, \ldots, a_n$。你的任务是确定，最少需要删除多少个元素，使得该数组变成好数组。
输入格式
每个测试包含若干组数据。第一行包含测试组数 $t$（$1 \le t \le 6 \cdot 10^4$）。接下来的每组数据描述如下。
每组数据的第一行包含一个整数 $n$（$1 \leq n \leq 3 \cdot 10^5$），表示数组中元素的个数。
每组数据的第二行包含 $n$ 个整数 $a_1$、$a_2$、$\ldots$、$a_n$（$1 \leq a_i \leq n$），表示数组的元素。
保证所有测试数据中 $n$ 的总和不超过 $3 \cdot 10^5$。
每组数据的第一行包含一个整数 $n$（$1 \leq n \leq 3 \cdot 10^5$），表示数组中元素的个数。
每组数据的第二行包含 $n$ 个整数 $a_1$、$a_2$、$\ldots$、$a_n$（$1 \leq a_i \leq n$），表示数组的元素。
保证所有测试数据中 $n$ 的总和不超过 $3 \cdot 10^5$。
输出格式
对于每组测试数据，输出一个整数，即使数组成为好数组所需删除的最少元素数目。
输入输出样例
输入 #1
6 1 1 5 1 2 3 4 5 5 5 4 3 2 1 5 5 5 5 4 4 7 1 7 1 2 5 7 1 6 1 2 5 6 5 5
输出 #1
0 2 0 0 1 2
说明/提示
在第一个测试用例中，数组本身就是好数组，所以不需要删除任何元素。
在第二个测试用例中，最优方案是删除数组中的第 2 个和第 4 个元素，这样得到数组 $1, 3, 5$。
在第三个测试用例中，数组本身就是好数组。
在第四个测试用例中，数组本身就是好数组。
在第五个测试用例中，最优方案是删除第 4 个元素，这样得到数组 $1, 7, 1, 5, 7, 1$。
在第六个测试用例中，一种最优方案是删除第 1 个和第 4 个元素，这样得到数组 $2, 5, 5, 5$。
在第二个测试用例中，最优方案是删除数组中的第 2 个和第 4 个元素，这样得到数组 $1, 3, 5$。
在第三个测试用例中，数组本身就是好数组。
在第四个测试用例中，数组本身就是好数组。
在第五个测试用例中，最优方案是删除第 4 个元素，这样得到数组 $1, 7, 1, 5, 7, 1$。
在第六个测试用例中，一种最优方案是删除第 1 个和第 4 个元素，这样得到数组 $2, 5, 5, 5$。