A16687 | $Locked Out$

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

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

C++ 编辑器

输入

输出