CF1927G.Paint Charges

A horizontal grid strip of $n$ cells is given. In the $i$-th cell, there is a paint charge of size $a_i$. This charge can be:

• either used to the left — then all cells to the left at a distance less than $a_i$ (from $\max(i - a_i + 1, 1)$ to $i$ inclusive) will be painted,
• or used to the right — then all cells to the right at a distance less than $a_i$ (from $i$ to $\min(i + a_i - 1, n)$ inclusive) will be painted,
• or not used at all.

Note that a charge can be used no more than once (that is, it cannot be used simultaneously to the left and to the right). It is allowed for a cell to be painted more than once.

What is the minimum number of times a charge needs to be used to paint all the cells of the strip?

给定一个包含 $n$ 个格子的水平网格条带。在第 $i$ 个格子中，有一个大小为 $a_i$ 的颜料电荷。该电荷可以：

• 向左使用——此时所有距离小于 $a_i$ 的左侧格子（即从 $\max(i - a_i + 1, 1)$ 到 $i$（含）的所有格子）将被涂色；
• 向右使用——此时所有距离小于 $a_i$ 的右侧格子（即从 $i$ 到 $\min(i + a_i - 1, n)$（含）的所有格子）将被涂色；
• 完全不使用。

注意：每个电荷最多只能使用一次（即不能同时向左和向右使用）。允许一个格子被多次涂色。

为使条带中所有格子均被涂色，最少需要使用多少次电荷？

The first line of the input contains an integer $t$ ($1 \le t \le 100$) — the number of test cases in the test. This is followed by descriptions of $t$ test cases.

Each test case is specified by two lines. The first one contains an integer $n$ ($1 \le n \le 100$) — the number of cells in the strip. The second line contains $n$ positive integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le n$), where $a_i$ is the size of the paint charge in the $i$-th cell from the left of the strip.

It is guaranteed that the sum of the values of $n$ in the test does not exceed $1000$.

输入的第一行包含一个整数 $t$（$1 \le t \le 100$），表示测试用例的数量。随后是 $t$ 个测试用例的描述。

每个测试用例由两行组成。第一行包含一个整数 $n$（$1 \le n \le 100$），表示条带中的单元格数量。第二行包含 $n$ 个正整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le n$），其中 $a_i$ 表示条带中从左往右第 $i$ 个单元格内的颜料容量。

保证所有测试用例中 $n$ 的总和不超过 $1000$。

For each test case, output the minimum number of times the charges need to be used to paint all the cells of the strip.

对于每个测试用例，输出将条带的所有单元格涂色所需的最小充能使用次数。

In the third test case of the example, it is sufficient to use the charge from the $1$-st cell to the right, then it will cover both cells $1$ and $2$.

In the ninth test case of the example, you need to:

• use the charge from the $3$-rd cell to the left, covering cells from the $1$-st to the $3$-rd;
• use the charge from the $5$-th cell to the left, covering cells from the $4$-th to the $5$-th;
• use the charge from the $7$-th cell to the left, covering cells from the $6$-th to the $7$-th.

In the eleventh test case of the example, you need to:

• use the charge from the $5$-th cell to the right, covering cells from the $5$-th to the $10$-th;
• use the charge from the $7$-th cell to the left, covering cells from the $1$-st to the $7$-th.

在示例的第三个测试用例中，只需使用第 $1$ 个单元格向右释放的电荷，即可覆盖第 $1$ 和第 $2$ 个单元格。

在示例的第九个测试用例中，你需要：

• 使用第 $3$ 个单元格向左释放的电荷，覆盖第 $1$ 至第 $3$ 个单元格；
• 使用第 $5$ 个单元格向左释放的电荷，覆盖第 $4$ 至第 $5$ 个单元格；
• 使用第 $7$ 个单元格向左释放的电荷，覆盖第 $6$ 至第 $7$ 个单元格。

在示例的第十一个测试用例中，你需要：

• 使用第 $5$ 个单元格向右释放的电荷，覆盖第 $5$ 至第 $10$ 个单元格；
• 使用第 $7$ 个单元格向左释放的电荷，覆盖第 $1$ 至第 $7$ 个单元格。