该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给您一个数字数组 $a_1, a_2, \ldots, a_n$ 。您的任务是阻止数组的某些元素，以尽量减少其成本。假设您阻塞下标为 $1 \leq b_1 < b_2 < \ldots < b_m \leq n$ 的元素。然后数组的成本计算为以下最大值：

• 被阻止元素的总和，即 $a_{b_1} + a_{b_2} + \ldots + a_{b_m}$ 。
• 当阻塞元素被移除时，数组被划分成的段的最大总和。即以下（ $m + 1$ ）个子数组的最大和：[ $1, b_1 − 1$ ]、[ $b_1 + 1, b_2 − 1$ ]、[ $\ldots$ ]、[ $b_{m−1} + 1, b_m - 1$ ]、[ $b_m + 1, n$ ]（[ $x,x − 1$ ] 形式的子数组中的数字之和被视为 $0$ ）。

例如，如果 $n = 6$ ，原始数组为[ $1, 4, 5, 3, 3, 2$ ]，并且你将位置 $2$ 和 $5$ 的元素挡住，那么数组的成本将是块元素 ( $4 + 3 = 7$ ) 以及子数组 ( $1$ , $5 + 3 = 8$ , $2$ ) 的总和，即 $\max(7,1,8,2) = 8$ 。

需要输出分块后数组的最小成本。

输入描述

输入的第一行包含一个整数 $t$ ( $1 \leq t \leq 30\,000$ ) - 查询数。

每个测试用例由两行组成。第一行包含一个整数 $n$ ( $1 \leq n \leq 10^5$ ) - 数组 $a$ 的长度。第二行包含 $n$ 个元素 $a_1, a_2, \ldots, a_n$ ( $1 \leq a_i \leq 10^9$ ) — 数组 $a$ 。

保证所有测试用例的 $n$ 之和不超过 $10^5$ 。

输出描述

对于每个测试用例，输出一个数字——阻塞数组的最小成本。

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

7
5
11

样例解释

第一个测试用例与语句中的数组匹配。要获得 $7$ 的成本，您需要阻塞位置 $2$ 和 $4$ 处的元素。在这种情况下，数组的成本计算为以下最大值：

• 被阻止元素的总和，即 $a_2 + a_4 = 7$ 。
• 移除阻塞元素时数组被划分成的段的最大总和，即 $a_1$ 、 $a_3$ 、 $a_5 + a_6 = \max(1,5,5) = 5$ 中的最大值。

所以成本是 $\max(7,5) = 7$ 。

在第二个测试用例中，您可以阻止位置 $1$ 和 $4$ 处的元素。

在第三个测试用例中，要获得答案 $11$ ，您可以在位置 $2$ 和 $5$ 处遮挡元素。还有其他方法可以获得此答案，例如阻止位置 $4$ 和 $6$ 。