阻断元素

• 时间限制：5 秒
• 内存限制：256 MiB

题目描述

给定数组 $a_1,a_2,\ldots,a_n$。你可以选择若干下标 $1\le b_1<b_2<\cdots<b_m\le n$，并阻断这些位置。

一次选择的代价定义为下列数值中的最大值：

• 所有被阻断元素之和 $a_{b_1}+a_{b_2}+\cdots+a_{b_m}$；
• 删除被阻断元素后，剩余的 $m+1$ 个连续段各自的元素和。

空段的元素和为 $0$。请最小化这次选择的代价。

输入格式

第一行包含测试用例数 $t$。

每个测试用例包含两行：第一行是数组长度 $n$，第二行是 $n$ 个正整数 $a_1,a_2,\ldots,a_n$。

输出格式

对每个测试用例输出一行一个整数，表示最小可能代价。

样例输入 1

3
6
1 4 5 3 3 2
5
1 2 3 4 5
6
4 1 6 3 10 7

样例输出 1

7
5
11

数据范围

对于所有数据，$1\le t\le30000$，$1\le n\le10^5$，$1\le a_i\le10^9$，且每个输入文件中 $\sum n\le10^5$。