Problem Description

It is snowing. Little Y stacked $n$ snow pillars in a row. Naughty little X wants to knock down these $n$ snow pillars. He wants to knock them all down in the least time, so he asks you to help him plan.

Each snow pillar stacked by little Y has height $a_i$ units. The time to manually push down one snow pillar equals the height of that pillar. Little X can only push snow pillars from the two ends of the row *, with no limit on the number of pushes. The time for little X to move can be ignored. In this way, a pillar can fall onto other pillars, knocking down another pillar (the time for knocking down is ignored), and then a chain reaction happens, saving more time **.

Let the initial potential energy be the height of the currently manually pushed pillar $k$, i.e. $p=a_k$. During this chain reaction, when the $i$-th pillar falls toward the $j$-th pillar:

• If $p\ge a_j$, then the $j$-th pillar is also knocked down, and set $p \gets a_j$.
• If $p< a_j$, then the height of the $j$-th pillar decreases (it is not knocked down), and the entire chain reaction stops. Set $a_j \gets a_j-p$.

Please find the minimum total time to knock down all snow pillars.

* Each time, you either push the leftmost pillar from the left side, or push the rightmost pillar from the right side.

** The falling direction depends on the pushing direction. If you push from the left, the pillars will fall to the right in order (the $i$-th pillar falls toward the $(i+1)$-th pillar), and vice versa.

Input Format

This problem has multiple test cases.

The first line contains an integer $T$, the number of test cases.

For each test case:

The first line contains an integer $n$, the number of snow pillars.

The second line contains $n$ integers, the heights of the snow pillars.

Output Format

For each test case, output one integer per line, the minimum time to knock down all snow pillars.

3
5
2 3 1 4 5
6 
6 6 6 6 6 6
6
1 1 4 5 1 4

7
6
8

Hint

Sample Explanation

• For the first test case:

Push from the left the first time, costing $2$ units of time, and the heights of the $5$ snow pillars become: $0,1,1,4,5$.

Push from the right the second time, costing $5$ units of time, and all pillars are knocked down.

The total time is $7$ units.

• For the second test case:

Pushing from either the left or the right can finish in one push, costing $6$ units of time in total.

• For the third test case:

Push from the right the first time, costing $4$ units of time, and the heights of the $6$ snow pillars become: $1,1,4,4,0,0$.

Push from the right the second time, costing $4$ units of time, and all pillars are knocked down.

The total time is $8$ units.

Constraints

This problem uses bundled testdata.

For all testdata, it is guaranteed that $1 \le T \le 10$, $1 \le n \le 10^5$, and $1 \le a_i \le 10^9$.

Translated by ChatGPT 5