← 返回题目列表

Codeforces · 2161/D

D. 被锁定

中文机器翻译题面 查看原题
谁阵好?你真是一个好阵! (三)

数组 $$$b$$$ 是 好 如果不存在索引 $$$1 \leq i \lt 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$$$。

输出

对于每个测试用例,打印一个整数 - 需要从数组中删除以使其成为良好数组的最小元素数。

示例

输入
复制

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

输出
复制

0
2
0
0
1
2

注意

在第一个测试用例中,数组从一开始就很好,因此不需要从中删除任何内容。

在第二个测试用例中,最佳解决方案是删除数组的第二个和第四个元素,这将产生 $$$1$$$、$$$3$$$、$$$5$$$ 数组。

在第三个测试用例中,数组从一开始就很好。

在第四个测试用例中,数组从一开始就很好。

在第五个测试用例中,最佳解决方案是删除数组的第四个元素,这将产生 $$$1$$$、$$$7$$$、$$$1$$$、$$$5$$$、$$$7$$$、$$$1$$$ 数组。

在第六个测试用例中,最佳解决方案之一是删除数组的第一个和第四个元素,这将产生 $$$2$$$、$$$5$$$、$$$5$$$、$$$5$$$ 数组。