Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

B. Сверхскорость
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Djjaner - Speedbreaker
⠀

В ряд стоят $$$n$$$ городов, пронумерованных $$$1, 2, \ldots, n$$$ слева направо.

  • В момент времени $$$1$$$ вы захватываете ровно один город, называемый начальным городом.
  • В моменты времени $$$2, 3, \ldots, n$$$ вы можете выбрать город, соседний с уже захваченным, и захватить его.

Вы выиграете, если для каждого $$$i$$$ вы захватите город $$$i$$$ в момент времени не позже, чем $$$a_i$$$. Выигрышная стратегия может существовать, а может и не существовать, в том числе в зависимости от стартового города. Сколько стартовых городов позволяют вам выиграть?

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество городов.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$) — сроки завоевания городов.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

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

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

В первом наборе входных данных города $$$2$$$, $$$3$$$ и $$$4$$$ являются подходящими стартовыми городами.

Во втором наборе входных данных нет подходящих стартовых городов.

В третьем наборе входных данных единственным подходящим стартовым городом является город $$$5$$$.