Вы играете в очередную компьютерную игру, где вы убиваете монстров с помощью магических заклинаний. Поле состоит из \(n\) клеток, расположенных в ряд и пронумерованных от \(1\) по \(n\). Первоначально, в \(i\)-й клетке находится \(i\)-й монстер с \(h_i\) единиц здоровья.
У вас есть базовое заклинание, которое стоит \(1\) MP и наносит \(1\) урона выбранному вами монстру. Вы можете использовать его любое количество раз. Также у вас есть свиток с заклинанием «Взрыв», которое вы можете использовать только один раз. Вы хотите закончить убийство монстров с помощью взрыва, а потому вы сначала используете базовое заклинание несколько раз (возможно, ни разу), а потом используете один «Взрыв».
Как же работает заклинание «Взрыв»? Во-первых, вы выбираете мощность заклинания: если вы вольете в него \(x\) MP, «Взрыв» нанесет \(x\) урона. Во-вторых, вы выбираете монстра \(i\), который будет целью заклинания. Вот что происходит дальше:
- если его текущее здоровье \(h_i > x\), то он остается живым со здоровьем, пониженным на \(x\);
- если \(h_i \le x\), то \(i\)-й монстр умирает и взрывается, нанося \(h_i - 1\) урона монстрам в соседних клетках \(i - 1\) и \(i + 1\), если эти клетки есть и монстры в них еще живы;
- если урона, нанесенного взрывом, достаточно, чтобы убить монстра \(i - 1\) (или \(i + 1\)), т. е. текущее \(h_{i - 1} \le h_i - 1\) (или \(h_{i + 1} \le h_i - 1\)), то этот монстр также взрывается, нанося \(h_{i-1} - 1\) (или \(h_{i+1} - 1\)) урона своим соседям, которые также могут взорваться, если умрут, и так далее.
Ваша задача — убить всех оставшихся монстров с помощью этих «цепных» взрывов, а потому вам может понадобиться базовое заклинание, чтобы уменьшить \(h_i\) некоторых монстров, а может, даже убить их заранее (монстры умирают, когда их текущее здоровье \(h_i\) становится меньше или равно нулю). Заметим, что монстры не перемещаются между клетками, а потому, например, монстры \(i\) и \(i + 2\) никогда не станут соседними.
Какое наименьшее суммарное MP вам нужно, чтобы уничтожить монстров описанным выше способом? Общее MP считается как сумма количества использований базового заклинания и выбранной мощности \(x\) заклинания «Взрыв».
Выходные данные
Для каждого набора входных данных выведите одно число — наименьшее суммарное количество MP, которое вам понадобится, для того, чтобы уничтожить всех монстров с помощью взрыва в конце.
Примечание
В первом наборе входных данных вы можете, например, использовать базовое заклинание на монстрах \(1\) и \(2\) (один раз на каждого), чтобы уничтожить их. После этого вы кастуете «Взрыв» мощности \(x = 1\) на монстра \(3\), чтобы убить его. Суммарное MP равно \(2 + 1 = 3\).
Во втором наборе, выгодно скастовать базовое заклинание \(4\) раза на монстра \(1\) и убить его. После этого, вы кастуете «Взрыв» мощности \(x = 2\) на монстра \(3\). Он умирает и взрывается с силой \(1\), чем убивает монстров \(2\) и \(4\). Суммарное MP равно \(4 + 2 = 6\).
В третьем наборе, вы кастуете «Взрыв» силы \(15\) на монстра \(3\). Взрыв \(3\)-го монстра (силы \(14\)) убивает монстров \(2\) и \(4\). Взрыв монстра \(2\) (силы \(9\)), в свою очередь, убивает монстра \(1\).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
3
1 1 1
4
4 1 2 1
4
5 10 15 10
1
42
9
1 2 3 2 2 2 3 2 1
|
3
6
15
42
12
|