涂料装置

• 时间限制：5 秒
• 内存限制：256 MiB

题目描述

给定一个长度为 $n$ 的水平网格带。第 $i$ 个格子中有一个大小为 $a_i$ 的涂料装置。每个装置可以选择下列三种行为之一：

• 向左使用，涂色区间 $[\max(i-a_i+1,1),i]$；
• 向右使用，涂色区间 $[i,\min(i+a_i-1,n)]$；
• 不使用。

每个装置至多使用一次，不能同时向左和向右使用。同一个格子可以被多次涂色。

求至少使用多少个装置，才能使整个网格带的所有格子都被涂色。

输入格式

第一行一个整数 $t$，表示测试用例数量。

每个测试用例第一行一个整数 $n$，第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

对每个测试用例输出一个整数，表示最少使用次数。

样例输入 1

13
1
1
2
1 1
2
2 1
2
1 2
2
2 2
3
1 1 1
3
3 1 2
3
1 3 1
7
1 2 3 1 2 4 2
7
2 1 1 1 2 3 1
10
2 2 5 1 6 1 8 2 8 2
6
2 1 2 1 1 2
6
1 1 4 1 3 2

样例输出 1

1
2
1
1
1
3
1
2
3
4
2
3
3

数据范围

• $1\le t\le100$；
• $1\le n\le100$；
• $1\le a_i\le n$；
• 单个输入文件内所有测试用例的 $n$ 之和不超过 $1000$。