Есть парк батутов с \(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\)?
Выходные данные
Для каждого набора входных данных выведите одно целое число — минимальное количество проходов, за которое Pekora может уменьшить все \(S_i\) до \(1\).
Примечание
Для первого набора входных данных, ниже приведена оптимальная последовательность проходов, которые 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\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
7
1 4 2 2 2 2 2
2
2 3
5
1 1 1 1 1
|
4
3
0
|