CFCF2161D.Locked Out

提高+/省选-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

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

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

输入#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

在第一个测试用例中，数组本身就是好数组，所以不需要删除任何元素。

在第二个测试用例中，最优方案是删除数组中的第 2 个和第 4 个元素，这样得到数组 $1, 3, 5$ 。

在第三个测试用例中，数组本身就是好数组。

在第四个测试用例中，数组本身就是好数组。

在第五个测试用例中，最优方案是删除第 4 个元素，这样得到数组 $1, 7, 1, 5, 7, 1$ 。

在第六个测试用例中，一种最优方案是删除第 1 个和第 4 个元素，这样得到数组 $2, 5, 5, 5$ 。