310752: CF1881E. Block Sequence

E. Block Sequencetime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Given a sequence of integers $a$ of length $n$.

A sequence is called beautiful if it has the form of a series of blocks, each starting with its length, i.e., first comes the length of the block, and then its elements. For example, the sequences [$\color{red}{3},\ \color{red}{3},\ \color{red}{4},\ \color{red}{5},\ \color{green}{2},\ \color{green}{6},\ \color{green}{1}$] and [$\color{red}{1},\ \color{red}{8},\ \color{green}{4},\ \color{green}{5},\ \color{green}{2},\ \color{green}{6},\ \color{green}{1}$] are beautiful (different blocks are colored differently), while [$1$], [$1,\ 4,\ 3$], [$3,\ 2,\ 1$] are not.

In one operation, you can remove any element from the sequence. What is the minimum number of operations required to make the given sequence beautiful?

Input

The first line of the input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then follows the descriptions of the test cases.

The first line of each test case contains a single integer $n$ ($1 \le n \le 2 \cdot 10^5$) — the length of the sequence $a$.

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$) — the elements of the sequence $a$.

It is guaranteed that the sum of the values of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output a single number — the minimum number of deletions required to make the sequence $a$ beautiful.

ExampleInput

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

Output

0
4
1
1
2
1
0

Note

In the first test case of the example, the given sequence is already beautiful, as shown in the statement.

In the second test case of the example, the sequence can only be made beautiful by removing all elements from it.

In the fifth test case of the example, the sequence can be made beautiful by removing the first and last elements. Then the sequence will become [$2,\ 3,\ 4$].

题目大意：
给定一个整数序列a的长度n。如果序列是一系列块的形状，每个块以它的长度开始，即首先是块的长度，然后是其元素，则该序列被称为“美丽”的。例如，序列[3, 3, 4, 5, 2, 6, 1]和[1, 8, 4, 5, 2, 6, 1]是“美丽”的（不同颜色的块表示不同的块），而[1]，[1, 4, 3]，[3, 2, 1]则不是。每次操作可以删除序列中的任意元素。问使给定的序列“美丽”所需的最小操作数是多少？

输入输出数据格式：
输入：
第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。然后是测试用例的描述。
每个测试用例的第一行包含一个整数n（1≤n≤2×10^5）——序列a的长度。
每个测试用例的第二行包含n个整数a_1, a_2, …, a_n（1≤a_i≤10^6）——序列a的元素。
保证所有测试用例的n值之和不超过2×10^5。

输出：
对于每个测试用例，输出一个数字——使序列a“美丽”所需的最小删除数量。

示例：
输入：
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

注意：
在示例的第一个测试用例中，给定的序列已经“美丽”，如题目描述所示。
在示例的第二个测试用例中，只能通过删除所有元素使序列变得“美丽”。
在示例的第五个测试用例中，可以通过删除第一个和最后一个元素使序列变得“美丽”，然后序列将变为[2, 3, 4]。题目大意： 给定一个整数序列a的长度n。如果序列是一系列块的形状，每个块以它的长度开始，即首先是块的长度，然后是其元素，则该序列被称为“美丽”的。例如，序列[3, 3, 4, 5, 2, 6, 1]和[1, 8, 4, 5, 2, 6, 1]是“美丽”的（不同颜色的块表示不同的块），而[1]，[1, 4, 3]，[3, 2, 1]则不是。每次操作可以删除序列中的任意元素。问使给定的序列“美丽”所需的最小操作数是多少？ 输入输出数据格式： 输入： 第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。然后是测试用例的描述。 每个测试用例的第一行包含一个整数n（1≤n≤2×10^5）——序列a的长度。 每个测试用例的第二行包含n个整数a_1, a_2, …, a_n（1≤a_i≤10^6）——序列a的元素。 保证所有测试用例的n值之和不超过2×10^5。 输出： 对于每个测试用例，输出一个数字——使序列a“美丽”所需的最小删除数量。 示例： 输入： 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 注意： 在示例的第一个测试用例中，给定的序列已经“美丽”，如题目描述所示。 在示例的第二个测试用例中，只能通过删除所有元素使序列变得“美丽”。 在示例的第五个测试用例中，可以通过删除第一个和最后一个元素使序列变得“美丽”，然后序列将变为[2, 3, 4]。