P10569 "Daily OI Round 4" Snow

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.

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

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

#### 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.** |$\text{Subtask}$|Score|$n \le$| | :-----------: | :-------------:|:-----------: | |$0$|$10$|$20$| |$1$|$15$|$100$| |$2$|$25$|$1000$| |$3$|$50$|$10^5$| 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