Explosions?
Contest: Educational Codeforces Round 143 (Rated for Div. 2)
Difficulty rating: 2200
Tags: binary search, data structures, dp, greedy, math

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.

Input format:
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$$$.

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

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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

Example input:
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

Example output:
3
6
15
42
12

Editorial:
Note that each unit of damage dealt by explosions save us from using one more basic spell. In other words, the more the damage from explosions, the better. So, the answer will be equal to $$$\sum{h_i} - (\text{maximum total damage from explosions})$$$.
Note that in order to kill all remaining monsters with the last spell, the array $$$h$$$ should have the following structure: there is a monster $$$p$$$ we cast the spell onto it and $$$h$$$ is strictly increasing in $$$[0..p]$$$ and strictly decreasing in $$$[p..n)$$$ (ignoring prefix and suffix of $$$0$$$-s).
Let's focus on the left part of array $$$h$$$ (segment $$$[0...p]$$$), since solving the right part is exactly the same. Maximizing the total damage is equivalent to maximizing the sum of $$$h_i$$$ right before the final spell. Note that we can use the straight greedy strategy: to kill the chosen monster $$$p$$$ we should use "Explosion" spell of power exactly $$$h_p$$$ — it's not optimal to make it either more or less powerful.
After that, monster $$$p$$$ will create an explosion of power $$$h_p - 1$$$. If $$$h_{p-1} > h_{p} - 1$$$ we must decrease it to exactly $$$h_{p} - 1$$$ to continue the chain of explosions of maximum total damage. If $$$h_{p-2} > h_{p} - 2$$$ we also decrease it to exactly $$$h_{p} - 2$$$ and so on. (The general formula is $$$h_{p - i} > h_{p} - i$$$).
This series will stop either if $$$h_{p} - i \le 0$$$ (or $$$i \ge h_p$$$), or there are no monsters left ($$$p - i < 0$$$), or we met the monster with $$$h_{p - i} \le h_{p} - i$$$. The two first cases are easy to check in constant time, so let's look at the last case. Suppose that monster position is equal to $$$j = p - i$$$, then $$$i = p - j$$$ or $$$h_{j} \le h_{p} - (p - j)$$$ $$$\leftrightarrow$$$ $$$h_{j} - j \le h_{p} - p$$$.
That monster $$$j$$$ is interesting to us because after death it creates an explosion of damage $$$h_{j} - 1$$$ that already doesn't depend on $$$p$$$ and next calculation is practically the same task: what chain of explosion we can have if we start from $$$j$$$. That idea drives us to dp: let $$$d[i]$$$ be the maximum damage of chaining explosion we can deal if we start from $$$i$$$ and move to the left. For simplicity, let's include $$$h_i$$$ into that total damage.
Calculating $$$d[i]$$$ is next: let's find the "first" $$$j$$$ such that $$$h_{j} - j \le h_{i} - i$$$. If there are no such $$$j$$$ (or if that $$$j$$$ is too far from $$$i$$$, i. e. $$$i - j \ge h_i$$$), we will set $$$j = \max(-1, i - h_i)$$$.
Now we know that on interval $$$(j, i]$$$ the damage dealt is the arithmetic progression: for $$$i$$$ it's $$$h_i$$$, for $$$i - 1$$$ it's $$$h_i - 1$$$, ..., for $$$j + 1$$$ it's $$$h_i - (i - j) + 1$$$. In total, $$$d[i] = (i - j) h_i - \frac{(i - j) (i - j - 1)}{2}$$$. And if such $$$j$$$ exists and not too far away, we increase $$$d[i]$$$ by $$$d[j]$$$ as well.
The last question is finding for each $$$i$$$ the closest $$$j < i$$$ such that $$$a_j - i \le a_i - i$$$. Note that if we define $$$a'_i = a_i - i$$$, we need just need to find last $$$a'_j \le a'_i$$$ and that's quite standard task that can be solved with stack.
Let's iterate over $$$i$$$ and maintain a stack of previous $$$a'_i$$$. When we need to find $$$j$$$ for the current $$$a'_i$$$ let's just look at the top of the stack: if $$$a'_j \le a'_i$$$ we found $$$j$$$ we wanted, otherwise just pop it and check the new top again and so on, until either we find $$$j$$$ or stack becomes empty that would mean that there are no $$$a'_j \le a'_i$$$. After processing the $$$i$$$-th element, push $$$a'_i$$$ on top of the stack.
Why it works? Consider some $$$i$$$. The element on top of the stack is $$$a'_j$$$ (firstly, it's $$$a'_{i-1}$$$ but we are talking about general case). If $$$a'_j \le a'_i$$$ we found what we want. Otherwise, $$$a'_j > a'_i$$$ but it also means that previous elements $$$a'_k$$$, that was popped on previous iteration $$$j$$$, was greater than $$$a'_j$$$. So, $$$a'_k$$$ is bigger than $$$a'_i$$$ as well, and there were no need to even consider them, i. e. popping them out earlier doesn't break anything.
Since each element is pushed in the stack once and popped out once, then the complexity is $$$O(n)$$$ for all $$$i$$$ for $$$1$$$ to $$$n$$$, or $$$O(1)$$$ amortized.
The answer for the chosen position $$$p$$$ then is $$$\sum{h_i} - dL[p] - dR[p] + 2 h_p$$$ where $$$dL[p]$$$ is dp we discussed above, $$$dR[p]$$$ is the same dp but on reversed array $$$h$$$ and $$$2 h_p$$$ because we included $$$h_p$$$ into both $$$dL[p]$$$ and $$$dR[p]$$$.
Both $$$dL$$$ and $$$dR$$$ are calculated in $$$O(n)$$$, so the total comlpexity is $$$O(n)$$$.