Explosions?

### 题目大意 你在玩一个利用魔法杀怪物的游戏。具体地，有一排 $n$ 个格子，第 $i$ 个格子里有编号为 $i$、初始生命值为 $h_i$ 的怪物。怪物生命值小于等于 $0$ 则被杀死，所有怪物被杀死则游戏结束。 你有两种攻击方式：一种是普通攻击，你将消耗 $1$ 点能量对选中的怪物进行 $1$ 点伤害（也就是怪物的生命值减 $1$），你可以使用普通攻击任意次数。同时，你还可以使用恰好一次“爆炸”攻击。你想要游戏以“爆炸”攻击结束，也就是说，你会先进行若干次普通攻击（可以为 $0$ 次），然后使用一次“爆炸”攻击结束游戏。 “爆炸”攻击的机制如下：你可以选择消耗的能量数 $x$，然后选中一个怪物 $i$，之后： - 若怪物 $i$ 当前的生命值 $h_i > x$，那么该怪物生命值减去 $x$； - 若 $h_i\le x$，则该怪物被击杀，同时向两旁的怪物（即第 $i-1$ 和 $i+1$ 只怪物，如果有且还存活的话）造成 $h_i - 1$ 的伤害； - 若 $h_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$）的伤害。如此循环只到杀不死一直怪物为止。 你的目标就是先用普通攻击减少某些怪物的生命值或直接杀死某些怪物，然后用这样“链式”的“爆炸”攻击杀死所有怪物。注意怪物不会移动，例如第 $i$ 只怪物和第 $i+2$ 只怪物永远不会相邻。 你需要消耗最少的能量值来达成目标（包括普通攻击和“爆炸”攻击的），求出这个最小值。 ### 输入格式 输入第一行一个正整数 $t$（$1\le t\le 10^4$）表示测试数据组数。 每组测试数据第一行一个正整数 $n$（$1\le n\le 3\cdot 10^5$）表示怪物数量； 第二行 $n$ 个正整数 $h_1,h_2,\ldots,h_n$（$1\le h_i\le 10^6$）依次表示怪物的生命值。 保证所有测试数据的 $n$ 之和不超过 $3\cdot 10^5$。 ### 输出格式 输出一行一个正整数表示杀死所有怪物所需要消耗的最小能量值。

You are playing yet another game where you kill monsters using magic spells. There are $ n $ cells in the row, numbered from $ 1 $ to $ n $ . Initially, the $ i $ -th cell contains the $ i $ -th monster with $ h_i $ health. You have a basic spell that costs $ 1 $ MP and deals $ 1 $ damage to the monster you choose. You can cast it any number of times. Also, you have a special scroll with "Explosion" spell you can use only once. You want to finish killing monsters with explosion, that's why you, firstly, cast the basic spell several times (possibly, zero), and then after that, you cast one "Explosion". How does "Explosion" spell work? Firstly, you choose the power of the spell: if you pour $ x $ MP into it, "Explosion" will deal $ x $ damage. Secondly, you choose some monster $ i $ , which will be targeted by the spell. That's what happens next: - if its current health $ h_i > x $ , then he stays alive with health decreased by $ x $ ; - if $ h_i \le x $ , the $ i $ -th monster dies with an explosion that deals $ h_i - 1 $ damage to monsters in the neighboring cells $ i - 1 $ and $ i + 1 $ , if these cells exist and monsters inside are still alive; - if the damage dealt by the explosion is enough to kill the monster $ i - 1 $ (or $ i + 1 $ ), i. e. the current $ h_{i - 1} \le h_i - 1 $ (or $ h_{i + 1} \le h_i - 1 $ ), then that monster also dies creating a secondary explosion of power $ h_{i-1} - 1 $ (or $ h_{i+1} - 1 $ ) that may deals damage to their neighbors, and so on, until the explosions end. Your goal is to kill all the remaining monsters with those "chaining" explosions, that's why you need a basic spell to decrease $ h_i $ of some monsters or even kill them beforehand (monsters die when their current health $ h_i $ becomes less or equal to zero). Note that monsters don't move between cells, so, for example, monsters $ i $ and $ i + 2 $ will never become neighbors. What is the minimum total MP you need to kill all monsters in the way you want? The total MP is counted as the sum of the number of basic spells you cast and the power $ x $ of explosion scroll you've chosen.

The first line contains one integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. The first line of each test case contains the single integer $ n $ ( $ 1 \le n \le 3 \cdot 10^5 $ ) — the number of cells in the row, i. e. the number of monsters. The second line of each test case contains $ n $ integers $ h_1, h_2, \dots, h_n $ ( $ 1 \le h_i \le 10^6 $ ) — the initial health of the monsters. It's guaranteed that the sum of $ n $ over all test cases doesn't exceed $ 3 \cdot 10^5 $ .

For each test case, print one integer — the minimum total MP you need to kill all monsters by finishing them with explosion.

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

In the first test case, you can, for example, use basic spell on monsters $ 1 $ and $ 2 $ (once per monster) to kill them. After that, you cast "Explosion" of power $ x = 1 $ on monster $ 3 $ to kill it. The total MP you need is $ 2 + 1 = 3 $ . In the second test case, it's optimal to cast basic spell $ 4 $ times onto monster $ 1 $ to kill it. After that, you can cast "Explosion" of power $ x = 2 $ onto monster $ 3 $ . It dies, creating an explosion of power $ 1 $ that kills monsters $ 2 $ and $ 4 $ . The total MP you need is $ 4 + 2 = 6 $ . In the third test case, you cast "Explosion" of power $ 15 $ onto monster $ 3 $ . Explosion of the $ 3 $ -rd monster (of power $ 14 $ ) kills monsters $ 2 $ and $ 4 $ . Secondary explosion of monster $ 2 $ (of power $ 9 $ ) kills monster $ 1 $ .