← 返回题目列表

Codeforces · 1881/E

E. 块顺序

中文机器翻译题面 查看原题

给定一个长度为 $$$n$$$ 的整数序列 $$$a$$$。

如果一个序列具有一系列块的形式,每个块都以其长度开始,即首先是块的长度,然后是它的元素,则该序列被称为美丽的。例如,序列 [$$$\color{red}{3},\ \color{red}{3},\ \color{red}{4},\ \color{red}{5},\ \color{green}{2},\ \color{green}{6},\ \color{green}{1}$$$] 和 [$$$\color{red}{1},\ \color{red}{8},\ \color{green}{4},\ \color{green}{5},\ \color{green}{2},\ \color{green}{6},\ \color{green}{1}$$$] 很漂亮(不同的方块颜色不同),而 [$$$1$$$], [$$$1,\ 4,\ 3$$$], [$$$3,\ 2,\ 1$$$] 则不然。

在一次操作中,您可以从序列中删除任何元素。使给定序列变得漂亮所需的最少操作次数是多少?

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。然后是测试用例的描述。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 序列 $$$a$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — 序列 $$$a$$$ 的元素。

保证所有测试用例的 $$$n$$$ 值之和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出一个数字 - 使序列 $$$a$$$ 漂亮所需的最小删除次数。

示例

输入 #1

7
7
3 3 4 5 2 6 1
4
5 6 3 2
6
3 4 1 6 7 7
3
1 4 3
5
1 2 3 4 5
5
1 2 3 1 2
5
4 5 5 1 5

输出 #1

0
4
1
1
2
1
0

注意

在示例的第一个测试用例中,给定的序列已经很漂亮,如语句所示。

在示例的第二个测试用例中,只能通过删除其中的所有元素来使序列变得漂亮。

在示例的第五个测试用例中,可以通过删除第一个和最后一个元素来使序列变得漂亮。那么序列就会变成[$$$2,\3,\4$$$]。