CF1881E.Block Sequence

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?

给定一个长度为 $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$] 则不是。

每次操作中，你可以从序列中删除任意一个元素。问：使给定序列变为优美序列所需的最少操作次数是多少？

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$.

输入的第一行包含一个整数 $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$。

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

对于每个测试用例，输出一个整数——使序列 $a$ 变为“优美”的最少删除次数。

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$].

在示例的第一个测试用例中，给定序列本身已是优美的，如题面所述。

在示例的第二个测试用例中，该序列只能通过移除其中所有元素才能变得优美。

在示例的第五个测试用例中，该序列可通过移除第一个和最后一个元素而变得优美。此时序列将变为 [$2,\ 3,\ 4$]。