Gildong разрабатывает новую головоломку. Головоломка состоит из \(n\) платформ, пронумерованных от \(1\) до \(n\). Игрок играет за персонажа, который может стоять на платформах и цель игры это передвинуть персонажа с \(1\)-й платформы на \(n\)-ю. На \(i\)-й платформе записано число \(a_i\) (\(0 \le a_i \le n-i\)). Когда персонаж стоит на \(i\)-й платформе, игрок может передвинуть его на \(j\)-ю платформу, для \(i+1 \le j \le i+a_i\). Если игрок находится на \(i\)-й платформе, что \(a_i=0\) и \(i \ne n\), игрок проигрывает.
Так как Gildong думает, что текущая игра слишком простая, он хочет сделать ее еще сложнее. Он хочет поменять несколько (возможно, ноль) чисел на платформах на \(0\), чтобы остался ровно один способ выиграть. Он хочет вносить как можно меньше изменений в игру, так что он просит вас найти минимальное количество платформ, у которых нужно изменить числа. Два способа выиграть считаются различными, если существует платформа, на которой был персонаж в одном способе, но не был в другом.
Выходные данные
Для каждого набора входных данных, выведите одно целое число — минимальное количество номеров, которое нужно поменять на \(0\), чтобы существовал ровно один способ выиграть.
Примечание
В первом наборе входных данных, игрок может двигать только на следующую платформу, пока он не доберется до \(4\)-й платформы. Так как исходно есть ровно один способ выиграть, ответ равен нулю.
Во втором наборе входных данных, Gildong может поменять \(a_2\), \(a_3\), и \(a_4\) на \(0\), чтобы игра стала \(4\) \(0\) \(0\) \(0\) \(0\). Теперь единственный способ выиграть, это прыгнуть с \(1\)-й платформы на \(5\)-ю платформу.
В третьем наборе входных данных, Gildong может поменять \(a_2\) и \(a_8\) на \(0\), тогда единственный способ выиграть это: \(1\) – \(3\) – \(7\) – \(9\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
4
1 1 1 0
5
4 3 2 1 0
9
4 1 4 2 1 0 2 1 0
|
0
3
2
|