E. Взрывы?
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вы играете в очередную компьютерную игру, где вы убиваете монстров с помощью магических заклинаний. Поле состоит из $$$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$$$ заклинания «Взрыв».

Входные данные

В первой строке задано одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных.

В первой строке каждого набора задано одно целое число $$$n$$$ ($$$1 \le n \le 3 \cdot 10^5$$$) — количество клеток на поле, или же количество монстров.

Во второй строке каждого набора заданы $$$n$$$ целых чисел $$$h_1, h_2, \dots, h_n$$$ ($$$1 \le h_i \le 10^6$$$) — первоначальное здоровье монстров.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$3 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно число — наименьшее суммарное количество MP, которое вам понадобится, для того, чтобы уничтожить всех монстров с помощью взрыва в конце.

Пример
Входные данные
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
Примечание

В первом наборе входных данных вы можете, например, использовать базовое заклинание на монстрах $$$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$$$.