给出了 $$$n$$$ 个单元格的水平网格带。在第 $$$i$$$ 个单元中,有大小为 $$$a_i$$$ 的油漆费用。该费用可以是:
- 要么用于左侧 - 那么左侧距离小于 $$$a_i$$$ 的所有单元格(从 $$$\max(i - a_i + 1, 1)$$$ 到 $$$i$$$ 包括在内)将被绘制,
- 或用于右侧 - 那么右侧距离小于 $$$a_i$$$ 的所有单元格(从 $$$i$$$ 到 $$$\min(i + a_i - 1, n)$$$ 包括)将被绘制,
- 或根本不使用。
请注意,一次充能只能使用一次(即不能同时向左和向右使用)。允许一个单元被多次绘制。
一次充电需要使用最少多少次来绘制条带的所有单元?
输入
输入的第一行包含一个整数 $$$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$$$。
输出
对于每个测试用例,输出绘制条带的所有单元所需的电荷的最小次数。
示例
输入 #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$$$-st 单元格的电荷就足够了,然后它将覆盖 $$$1$$$ 和 $$$2$$$ 两个单元格。
在示例的第九个测试用例中,您需要:
- 使用左侧 $$$3$$$-rd 单元格的电荷,覆盖从 $$$1$$$-st 到 $$$3$$$-rd 的单元格;
- 使用左侧第 $$$5$$$ 个单元格的电荷,覆盖从第 $$$4$$$ 到第 $$$5$$$ 的单元格;
- 使用左侧第 $$$7$$$ 个单元格的电荷,覆盖从第 $$$6$$$ 到第 $$$7$$$ 的单元格。
在示例的第十一个测试用例中,您需要:
- 使用右侧第$$$5$$$个单元格的电荷,覆盖从第$$$5$$$个单元格到第$$$10$$$个单元格;
- 使用左侧第 $$$7$$$ 单元格的电荷,覆盖从 $$$1$$$ 单元格到第 $$$7$$$ 单元格。