CF1918D.Blocking Elements

You are given an array of numbers $a_1, a_2, \ldots, a_n$. Your task is to block some elements of the array in order to minimize its cost. Suppose you block the elements with indices $1 \leq b_1 \lt b_2 \lt \ldots \lt b_m \leq n$. Then the cost of the array is calculated as the maximum of:

• the sum of the blocked elements, i.e., $a_{b_1} + a_{b_2} + \ldots + a_{b_m}$.
• the maximum sum of the segments into which the array is divided when the blocked elements are removed. That is, the maximum sum of the following ($m + 1$) subarrays: [$1, b_1 − 1$], [$b_1 + 1, b_2 − 1$], [$\ldots$], [$b_{m−1} + 1, b_m - 1$], [$b_m + 1, n$] (the sum of numbers in a subarray of the form [$x,x − 1$] is considered to be $0$).

For example, if $n = 6$, the original array is [$1, 4, 5, 3, 3, 2$], and you block the elements at positions $2$ and $5$, then the cost of the array will be the maximum of the sum of the blocked elements ($4 + 3 = 7$) and the sums of the subarrays ($1$, $5 + 3 = 8$, $2$), which is $\max(7,1,8,2) = 8$.

You need to output the minimum cost of the array after blocking.

给你一个数字数组 $a_1, a_2, \ldots, a_n$。你的任务是屏蔽（block）数组中的一些元素，以使数组的代价（cost）最小化。假设你屏蔽了下标为 $1 \leq b_1 \lt b_2 \lt \ldots \lt b_m \leq n$ 的元素。则该数组的代价定义为以下两项中的最大值：

• 被屏蔽元素的和，即 $a_{b_1} + a_{b_2} + \ldots + a_{b_m}$；
• 当被屏蔽元素被移除后，原数组被分割成的若干连续段（segments）中，各段元素之和的最大值。具体而言，这些段对应如下 $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$ 上的元素（即屏蔽 $a_2 = 4$ 和 $a_5 = 3$），则数组代价为以下各项的最大值：被屏蔽元素之和（$4 + 3 = 7$），以及各剩余连续段的和（[$1$] 的和为 $1$，[$3,4$] 即 $a_3+a_4 = 5+3 = 8$，[$6$] 即 $a_6 = 2$），即 $\max(7,1,8,2) = 8$。

你需要输出在最优屏蔽策略下，该数组所能达到的最小代价。

The first line of the input contains a single integer $t$ ($1 \leq t \leq 30\,000$) — the number of queries.

Each test case consists of two lines. The first line contains an integer $n$ ($1 \leq n \leq 10^5$) — the length of the array $a$. The second line contains $n$ elements $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^9$) — the array $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

输入的第一行包含一个整数 $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$。

For each test case, output a single number — the minimum cost of blocking the array.

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

The first test case matches with the array from the statement. To obtain a cost of $7$, you need to block the elements at positions $2$ and $4$. In this case, the cost of the array is calculated as the maximum of:

• the sum of the blocked elements, which is $a_2 + a_4 = 7$.
• the maximum sum of the segments into which the array is divided when the blocked elements are removed, i.e., the maximum of $a_1$, $a_3$, $a_5 + a_6 = \max(1,5,5) = 5$.

So the cost is $\max(7,5) = 7$.

In the second test case, you can block the elements at positions $1$ and $4$.

In the third test case, to obtain the answer $11$, you can block the elements at positions $2$ and $5$. There are other ways to get this answer, for example, blocking positions $4$ and $6$.

第一个测试用例对应题目描述中的数组。为了得到代价 $7$，你需要阻塞位置 $2$ 和 $4$ 上的元素。此时，该数组的代价定义为以下两者的最大值：

• 被阻塞元素的和，即 $a_2 + a_4 = 7$；
• 移除被阻塞元素后，数组被分割成若干连续段，这些段各自元素和的最大值，即 $\max(a_1,\,a_3,\,a_5 + a_6) = \max(1,5,5) = 5$。

因此，总代价为 $\max(7,5) = 7$。

在第二个测试用例中，你可以阻塞位置 $1$ 和 $4$ 上的元素。

在第三个测试用例中，为得到答案 $11$，你可以阻塞位置 $2$ 和 $5$ 上的元素。还有其他方式也能得到该答案，例如阻塞位置 $4$ 和 $6$。