C. Pekora и батуты
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Есть парк батутов с $$$n$$$ батутами, расположенными в ряд. $$$i$$$-й из них имеет силу $$$S_i$$$.

Pekora может прыгать по батутам в несколько проходов. Она начинает проход, прыгая на любой батут по своему выбору.

Если сейчас Pekora прыгает на батут $$$i$$$, то батут подбросит ее в позицию $$$i + S_i$$$, а $$$S_i$$$ станет равно $$$\max(S_i-1,1)$$$. Иначе говоря, $$$S_i$$$ уменьшится на $$$1$$$, кроме случая $$$S_i=1$$$, когда $$$S_i$$$ останется равно $$$1$$$.

Если в позиции $$$i + S_i$$$ нет батута, то этот проход завершен. В противном случае Pekora продолжит проход прыжком с батута в позиции $$$i + S_i$$$ по принципу, описанному выше.

Pekora не может перестать прыгать во время прохода, пока не приземлится на позицию больше $$$n$$$ (в которой нет батута). Бедная Pekora!

Pekora — непослушный кролик, и хочет разрушить парк батутов, уменьшив все $$$S_i$$$ до $$$1$$$. Какое минимальное количество проходов ей нужно, чтобы уменьшить все $$$S_i$$$ до $$$1$$$?

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

В первой строке содержится одно целое число $$$t$$$ ($$$1 \le t \le 500$$$) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 5000$$$) — количество батутов.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$S_1, S_2, \dots, S_n$$$ ($$$1 \le S_i \le 10^9$$$), где $$$S_i$$$ — это сила $$$i$$$-го батута.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$5000$$$.

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

Для каждого набора входных данных выведите одно целое число — минимальное количество проходов, за которое Pekora может уменьшить все $$$S_i$$$ до $$$1$$$.

Пример
Входные данные
3
7
1 4 2 2 2 2 2
2
2 3
5
1 1 1 1 1
Выходные данные
4
3
0
Примечание

Для первого набора входных данных, ниже приведена оптимальная последовательность проходов, которые Pekora может использовать. (Жирным выделены позиции батутов, куда прыгает Pekora в очередной проход).

  • $$$[1,4,\textbf{2},2,\textbf{2},2,\textbf{2}]$$$
  • $$$[1,\textbf{4},1,2,1,\textbf{2},1]$$$
  • $$$[1,\textbf{3},1,2,\textbf{1},\textbf{1},\textbf{1}]$$$
  • $$$[1,\textbf{2},1,\textbf{2},1,\textbf{1},\textbf{1}]$$$

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

  • $$$[\textbf{2},3]$$$
  • $$$[1,\textbf{3}]$$$
  • $$$[1,\textbf{2}]$$$

Для третьего набора входных данных, все $$$S_i$$$ уже равны $$$1$$$.