G. Заряды с краской
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задана горизонтальная клетчатая полоса из $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите минимальное количество раз, сколько необходимо использовать заряды, чтобы покрасить все клетки полосы.

Пример
Входные данные
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
2
1
1
1
3
1
2
3
4
2
3
3
Примечание

В третьем наборе входных данных примера достаточно использовать заряд из $$$1$$$-й клетки вправо, тогда он покроет обе клетки $$$1$$$ и $$$2$$$.

В девятом наборе входных данных примера нужно:

  • использовать заряд из $$$3$$$-й клетки влево, покрыв клетки от $$$1$$$-й до $$$3$$$-й;
  • использовать заряд из $$$5$$$-й клетки влево, покрыв клетки от $$$4$$$-й до $$$5$$$-й;
  • использовать заряд из $$$7$$$-й клетки влево, покрыв клетки от $$$6$$$-й до $$$7$$$-й.

В одиннадцатом наборе входных данных примера нужно:

  • использовать заряд из $$$5$$$-й клетки вправо, покрыв клетки от $$$5$$$-й до $$$10$$$-й;
  • использовать заряд из $$$7$$$-й клетки влево, покрыв клетки от $$$1$$$-й до $$$7$$$-й.