题目描述

给定一个长度为 $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$ 变为美丽序列所需删除的最小元素个数。

说明/提示

在样例的第一个测试用例中，给定的序列已经是美丽序列，如题目描述所示。

在样例的第二个测试用例中，只有将所有元素都删除才能使其成为美丽序列。

在样例的第五个测试用例中，可以通过删除第一个和最后一个元素使序列变为 [$2,\ 3,\ 4$]。

由 ChatGPT 4.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

0
4
1
1
2
1
0