В ряд стоят \(n\) городов, пронумерованных \(1, 2, \ldots, n\) слева направо.
- В момент времени \(1\) вы захватываете ровно один город, называемый начальным городом.
- В моменты времени \(2, 3, \ldots, n\) вы можете выбрать город, соседний с уже захваченным, и захватить его.
Вы выиграете, если для каждого \(i\) вы захватите город \(i\) в момент времени не позже, чем \(a_i\). Выигрышная стратегия может существовать, а может и не существовать, в том числе в зависимости от стартового города. Сколько стартовых городов позволяют вам выиграть?
Выходные данные
Для каждого набора входных данных выведите одно целое число: количество стартовых городов, которые позволяют вам выиграть.
Примечание
В первом наборе входных данных города \(2\), \(3\) и \(4\) являются подходящими стартовыми городами.
Во втором наборе входных данных нет подходящих стартовых городов.
В третьем наборе входных данных единственным подходящим стартовым городом является город \(5\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|