「Daily OI Round 4」Snow

下雪了，小 Y 堆了 $n$ 个雪柱排成一排，调皮的小 X 打算推倒这 $n$ 个雪柱，他想在最少的时间内推倒所有雪柱，于是他请你来为他出谋划策。 小 Y 堆的每个雪柱高 $a_i$ 单位，推倒一个雪柱的时间为该雪柱的高度。小 X 只能从这一排雪柱的两端推雪柱 \*，次数不限，小 X 移动的时间可以忽略不计。这样就可以使一个雪柱倒向其他雪柱，从而击倒另一个雪柱（击倒的时间忽略不计），然后发生连锁反应，更加节省时间 \*\*。 设初始的势能为当前手动推倒的雪柱 $k$ 的高度 $p=a_k$，则此轮连锁反应中第 $i$ 个雪柱倒向第 $j$ 个雪柱时： - 若 $p\ge a_j$，则使第 $j$ 个雪柱也被击倒，并令 $p \gets a_j$。 - 若 $p< a_j$，则第 $j$ 个雪柱的高度减少（不被击倒），终止整个连锁反应，令 $a_j \gets a_j-p$。 请你求出推倒所有雪柱的最短时间。 \*：每一次要么从左边推最左边的雪柱，要么从右边推最右边的雪柱。 \*\*：雪柱的倒塌方向取决于推雪柱的方向，如果从左边推，雪柱就会向右依次倒塌（第 $i$ 个雪柱倒塌向第 $i+1$ 个雪柱），反之同理。

**本题有多组测试数据。** 第一行一个整数 $T$，表示数据组数。 对于每组数据： 第一行一个整数 $n$，表示雪柱的数量。 第二行 $n$ 个整数，分别表示每个雪柱的高度。

对于每组数据：输出一行一个整数，表示推倒所有雪柱的最短时间。

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

7
6
8

#### 【样例解释】 - **对于第一组数据：** > 第一次从左边推，耗费 $2$ 点时间，使得 $5$ 个雪柱 的高度分别变为：$0,1,1,4,5$。 > > 第二次从右边推，耗费 $5$ 点时间，使得所有雪柱都被击倒。 > > 共耗费 $7$ 点时间。 - **对于第二组数据：** > 从左边或者右边都可以一次性推完，共耗费 $6$ 点时间。 - **对于第三组数据：** > 第一次从右边推，耗费 $4$ 点时间，使得 $6$ 个雪柱的高度分别变为：$1,1,4,4,0,0$。 > > 第二次从右边推，耗费 $4$ 点时间，使得所有雪柱都被击倒。 > > 共耗费 $8$ 点时间。 #### 【数据范围】 **本题采用捆绑测试。** |$\text{Subtask}$|分值|$n \le$| | :-----------: | :-------------:|:-----------: | |$0$|$10$|$20$| |$1$|$15$|$100$| |$2$|$25$|$1000$| |$3$|$50$|$10^5$| 对于全部数据，保证：$1 \le T \le 10$，$1 \le n \le 10^5$，$1 \le a_i \le 10^9$。