Blocking Elements
Contest: Codeforces Round 922 (Div. 2)
Difficulty rating: 1900
Tags: binary search, data structures, dp, implementation, two pointers

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 < b_2 < \ldots < 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.

Input format:
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$$$.

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

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

Note:
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$$$.

Example input:
3
6
1 4 5 3 3 2
5
1 2 3 4 5
6
4 1 6 3 10 7

Example output:
7
5
11

Editorial:
Let's do a binary search. Suppose we know that the minimum possible cost is less than $$$l$$$ and not greater than $$$r$$$. Let's choose $$$m = (l+r)/2$$$. We need to learn how to check if the answer is less than or equal to $$$m$$$. We will calculate $$$dp_i$$$  — the minimum sum of blocked elements in the prefix up to $$$i$$$ if position $$$i$$$ is blocked, and on each of the subsegments without blocked elements, the sum of elements is less than or equal to $$$m$$$. Then $$$dp_i = a_i + \min(dp_j)$$$ for all $$$j$$$ such that the sum on the subsegment from $$$j+1$$$ to $$$i-1$$$ is less than or equal to $$$m$$$. Such $$$j$$$ form a segment, since $$$a_j$$$ is positive. We will maintain the boundaries of this segment. We will also maintain all $$$dp_j$$$ for $$$j$$$ inside this subsegment in the set. When moving from $$$i$$$ to $$$i+1$$$, we will move the left boundary of the subsegment until the sum on it becomes less than or equal to $$$m$$$, and remove $$$dp_j$$$ from the set, and also add $$$dp_i$$$ to the set. The minimum sum of blocked elements under the condition that the sum on all subsegments without blocked elements is less than or equal to $$$m$$$ can be found as the minimum among all $$$dp_i$$$ such that the sum from $$$i$$$ to $$$n$$$ is less than or equal to $$$m$$$. If this answer is less than or equal to $$$m$$$, then the answer to the problem is less than or equal to $$$m$$$, otherwise the answer is greater than $$$m$$$.
Time complexity: $$$O(n \log n \log 10^9)$$$ per test case.