给你一个数字数组 $$$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$$$。
输出
对于每个测试用例,输出一个数字——阻塞数组的最小成本。
示例
输入 #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
注意
第一个测试用例与语句中的数组匹配。要获得 $$$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$$$。