CF2161D Locked Out

什么样的数组才是好数组？你就是好数组！（c） 如果对于数组 $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$。

对于每组测试数据，输出一个整数，即使数组成为好数组所需删除的最少元素数目。

在第一个测试用例中，数组本身就是好数组，所以不需要删除任何元素。 在第二个测试用例中，最优方案是删除数组中的第 2 个和第 4 个元素，这样得到数组 $1, 3, 5$。 在第三个测试用例中，数组本身就是好数组。 在第四个测试用例中，数组本身就是好数组。 在第五个测试用例中，最优方案是删除第 4 个元素，这样得到数组 $1, 7, 1, 5, 7, 1$。 在第六个测试用例中，一种最优方案是删除第 1 个和第 4 个元素，这样得到数组 $2, 5, 5, 5$。 由 ChatGPT 5 翻译