题目描述

下雪了，小 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$ 点时间。

【数据范围】

本题采用捆绑测试。

对于全部数据，保证：$1 \le T \le 10$，$1 \le n \le 10^5$，$1 \le a_i \le 10^9$。