CF1795E.Explosions?

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 \gt 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.

你正在玩另一款使用魔法消灭怪物的游戏。一行中有 $n$ 个格子，编号从 $1$ 到 $n$。初始时，第 $i$ 个格子中包含第 $i$ 只怪物，其生命值为 $h_i$。

你拥有一种基础法术：消耗 $1$ 点法力值（MP），对任意一只选定的怪物造成 $1$ 点伤害。该法术可施放任意次数（包括零次）。此外，你还拥有一张特殊的卷轴，上面记载着“爆炸”法术，你仅能使用一次。你希望最终通过“爆炸”法术消灭所有怪物，因此你的策略是：先施放若干次（可能为零次）基础法术，然后施放一次“爆炸”法术。

“爆炸”法术如何生效？首先，你需要决定该法术的威力：若向其中注入 $x$ 点 MP，则“爆炸”将造成 $x$ 点伤害；其次，你需要选择一只目标怪物 $i$。接下来发生如下事件：

• 若该怪物当前生命值 $h_i > x$，则它存活，生命值减少 $x$；
• 若 $h_i \le x$，则第 $i$ 只怪物死亡，并引发一次爆炸，对相邻格子（即 $i-1$ 和 $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$），进而可能对其邻居造成伤害；如此连锁进行，直至所有爆炸终止。

你的目标是：仅依靠这些“连锁爆炸”消灭所有剩余怪物。因此，你需要预先使用基础法术降低某些怪物的生命值（甚至提前将其击杀——当怪物当前生命值 $h_i \le 0$ 时即视为死亡）。注意，怪物不会在格子间移动，例如，怪物 $i$ 与 $i+2$ 永远不会成为邻居。

请问：按上述方式消灭所有怪物所需的最小总法力值是多少？总法力值定义为：你施放的基础法术次数 + 你为“爆炸”卷轴选定的威力 $x$。

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$.

第一行包含一个整数 $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$。

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

对于每个测试用例，输出一个整数——即通过爆炸终结所有怪物所需的最小总魔法值（MP）。

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$.

在第一个测试用例中，例如，你可以对怪物 $1$ 和 $2$ 各使用一次基础法术来击杀它们。之后，你对怪物 $3$ 施放一次威力为 $x = 1$ 的“爆炸”法术来击杀它。总共需要的法力值（MP）为 $2 + 1 = 3$。

在第二个测试用例中，最优策略是向怪物 $1$ 施放 $4$ 次基础法术来击杀它。之后，你向怪物 $3$ 施放一次威力为 $x = 2$ 的“爆炸”法术。该怪物死亡并引发一次威力为 $1$ 的爆炸，从而击杀怪物 $2$ 和 $4$。总共需要的法力值（MP）为 $4 + 2 = 6$。

在第三个测试用例中，你向怪物 $3$ 施放一次威力为 $15$ 的“爆炸”法术。怪物 $3$ 死亡并引发一次威力为 $14$ 的爆炸，从而击杀怪物 $2$ 和 $4$；随后怪物 $2$ 死亡并引发一次威力为 $9$ 的次级爆炸，从而击杀怪物 $1$。