Задана горизонтальная клетчатая полоса из \(n\) клеток. В \(i\)-й клетке находится заряд краски величины \(a_i\). Этот заряд можно:
- либо использовать влево — тогда все клетки налево на расстоянии меньше \(a_i\) (то есть с \(\max(i - a_i + 1, 1)\) по \(i\) включительно) окажутся покрашены,
- либо использовать вправо — тогда все клетки направо на расстоянии меньше \(a_i\) (то есть с \(i\) по \(\min(i + a_i - 1, n)\) включительно) окажутся покрашены,
- либо не использовать заряд.
Обратите внимание, что заряд можно использовать не более одного раза (то есть его нельзя использовать одновременно и влево и вправо). Допустимо, что клетка окажется покрашена более одного раза.
Какое минимальное количество раз заряд необходимо использовать, чтобы покрасить все клетки полосы?
Выходные данные
Для каждого набора входных данных выведите минимальное количество раз, сколько необходимо использовать заряды, чтобы покрасить все клетки полосы.
Примечание
В третьем наборе входных данных примера достаточно использовать заряд из \(1\)-й клетки вправо, тогда он покроет обе клетки \(1\) и \(2\).
В девятом наборе входных данных примера нужно:
- использовать заряд из \(3\)-й клетки влево, покрыв клетки от \(1\)-й до \(3\)-й;
- использовать заряд из \(5\)-й клетки влево, покрыв клетки от \(4\)-й до \(5\)-й;
- использовать заряд из \(7\)-й клетки влево, покрыв клетки от \(6\)-й до \(7\)-й.
В одиннадцатом наборе входных данных примера нужно:
- использовать заряд из \(5\)-й клетки вправо, покрыв клетки от \(5\)-й до \(10\)-й;
- использовать заряд из \(7\)-й клетки влево, покрыв клетки от \(1\)-й до \(7\)-й.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
13
1
1
2
1 1
2
2 1
2
1 2
2
2 2
3
1 1 1
3
3 1 2
3
1 3 1
7
1 2 3 1 2 4 2
7
2 1 1 1 2 3 1
10
2 2 5 1 6 1 8 2 8 2
6
2 1 2 1 1 2
6
1 1 4 1 3 2
|
1
2
1
1
1
3
1
2
3
4
2
3
3
|