Hills and Pits
Contest: Codeforces Round 980 (Div. 1)
Difficulty rating: 3500
Tags: data structures, greedy, math, matrices

In a desert city with a hilly landscape, the city hall decided to level the road surface by purchasing a dump truck. The road is divided into $$$n$$$ sections, numbered from $$$1$$$ to $$$n$$$ from left to right. The height of the surface in the $$$i$$$-th section is equal to $$$a_i$$$. If the height of the $$$i$$$-th section is greater than $$$0$$$, then the dump truck must take sand from the $$$i$$$-th section of the road, and if the height of the $$$i$$$-th section is less than $$$0$$$, the dump truck must fill the pit in the $$$i$$$-th section of the road with sand. It is guaranteed that the initial heights are not equal to $$$0$$$.

When the dump truck is in the $$$i$$$-th section of the road, it can either take away $$$x$$$ units of sand, in which case the height of the surface in the $$$i$$$-th section will decrease by $$$x$$$, or it can fill in $$$x$$$ units of sand (provided that it currently has at least $$$x$$$ units of sand in its bed), in which case the height of the surface in the $$$i$$$-th section of the road will increase by $$$x$$$.

The dump truck can start its journey from any section of the road. Moving to an adjacent section on the left or right takes $$$1$$$ minute, and the time for loading and unloading sand can be neglected. The dump truck has an infinite capacity and is initially empty.

You need to find the minimum time required for the dump truck to level the sand so that the height in each section becomes equal to $$$0$$$. Note that after all movements, the dump truck may still have sand left in its bed. You need to solve this problem independently for the segments numbered from $$$l_i$$$ to $$$r_i$$$. Sand outside the segment cannot be used.

Input format:
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 3 \cdot 10^5$$$) — the number of sections and the number of queries.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$, $$$a_i \neq 0$$$) — the initial height in each section.

The $$$i$$$-th of the following $$$q$$$ lines contains two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — the boundaries of the segment of sections for which the minimum time needs to be determined.

It is guaranteed that the sum of $$$n$$$ over all test cases and the sum of $$$q$$$ over all test cases do not exceed $$$3 \cdot 10^5$$$.

Output format:
For each query, output the minimum time required to level the sand in the segment $$$[l_i, r_i]$$$, or $$$-1$$$ if it is impossible.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
In the first test case, $$$179$$$ units of sand need to be added to the only section. However, there is nowhere to take it from, so this is impossible.

In the second test case:

- In the first query, the dump truck can start its journey at the second section. It can take $$$2$$$ units of sand, after which the height in the second section will become $$$0$$$. Then the dump truck can move to the third section. It can pour $$$1$$$ unit of sand there, after which the height in the third section will become $$$0$$$. Then the dump truck can move to the fourth section. There it can take $$$3$$$ units of sand, after which the height in the fourth section will become $$$0$$$. In total, the dump truck will spend $$$2$$$ minutes on movements.
- In the second query, the dump truck can start its journey at the fourth section. It can take $$$3$$$ units of sand, after which the height in the fourth section will become $$$0$$$. Then the dump truck can move to the fifth section. It can pour $$$1$$$ unit of sand there, after which the height in the fifth section will become $$$0$$$. Then the dump truck can move back to the fourth section and then to the third. It can pour $$$1$$$ unit of sand there, after which the height in the third section will become $$$0$$$. Then the dump truck can move to the second section. It can take $$$2$$$ units of sand. Then it can move to the first section. It can pour $$$2$$$ units of sand there, after which the height in the first section will become $$$0$$$. In total, the dump truck will spend $$$5$$$ minutes on movements.
- In the third query, the dump truck will not be able to make the height in each section equal to $$$0$$$.

Example input:
5
1 1
-179
1 1
5 3
-2 2 -1 3 -1
2 4
1 5
1 3
7 1
1 1 1 -4 1 1 1
1 7
7 2
2 -2 2 -2 1 2 -1
1 7
2 7
4 4
1000000000 1000000000 999999999 -1000000000
2 4
3 4
2 3
1 3

Example output:
-1
2
5
-1
8
6
6
2
-1
1
2

Editorial:
To begin, let's solve the problem for a single query, where $$$ l = 1 $$$ and $$$ r = n $$$.
We will introduce an additional constraint — the dump truck must start on the first segment and finish on the last one. We will calculate the prefix sums of the array $$$ a_1, a_2, \ldots, a_n $$$, denoted as $$$ p_1, p_2, \ldots, p_n $$$. If $$$ p_n < 0 $$$, then the answer is $$$-1$$$, as there won't be enough sand to cover all $$$ a_i < 0 $$$; otherwise, an answer exists. Let $$$ x_i $$$ be the number of times the dump truck travels between segments $$$ i $$$ and $$$ i+1 $$$ (in either direction). Notice that if $$$ p_i < 0 $$$, then $$$ x_i \geq 3 $$$. Since the dump truck starts to the left of segment $$$ i+1 $$$, it will have to pass through $$$ x_i $$$ once. Additionally, since $$$ p_i < 0 $$$, it will have to return to the prefix to balance it out (it won't have enough sand to cover the negative $$$ a_i $$$). Then it will have to pass through $$$ x_i $$$ a third time, as the dump truck must finish its journey to the right of segment $$$ i $$$. The dump truck can travel such that when $$$ p_i < 0 $$$, $$$ x_i = 3 $$$, and when $$$ p_i \geq 0 $$$, $$$ x_i = 1 $$$. To achieve this, it simply needs to travel from left to right, and if $$$ p_i \geq 0 $$$, it just returns left while traversing the negative prefix sums, nullifying the negative $$$ a_i $$$. If it reaches $$$ p_j \geq 0 $$$, then the entire prefix to the left of it has already been nullified (we maintain this invariant), and it simply returns right to $$$ p_i $$$. The entire prefix $$$ p_i $$$ is nullified. With this algorithm, we achieve $$$ x_i = 3 $$$ when $$$ p_i < 0 $$$ and $$$ x_i = 1 $$$ otherwise, which is the optimal answer to the problem.
Now, let's remove the constraint on the starting and ending positions of the dump truck. Let the dump truck start at segment $$$ s $$$ and finish at segment $$$ f $$$, with $$$ s \leq f $$$. Then, if $$$ i < s $$$, $$$ x_i \geq 2 $$$, since the dump truck starts and finishes to the right of segment $$$ i $$$, meaning it needs to reach it and then return right. Similarly, if $$$ i \geq f $$$, then $$$ x_i = 2 $$$. For all $$$ s \leq i < f $$$, the constraints on $$$ x_i $$$ described earlier still hold. How can we now achieve optimal $$$ x_i $$$? Let the dump truck travel from $$$ s $$$ to $$$ 1 $$$, nullifying all $$$ a_i > 0 $$$ and collecting sand, and then travel right to $$$ s $$$, covering all $$$ a_i < 0 $$$ (here we used the fact that $$$ p_s \geq 0 $$$, which we will prove later). From $$$ s $$$ to $$$ f $$$, the dump truck follows the previously described algorithm for $$$ s = 1 $$$ and $$$ f = n $$$. Next, it will travel from $$$ f $$$ to $$$ n $$$, nullifying $$$ a_i > 0 $$$, and then return to $$$ f $$$, covering $$$ a_i < 0 $$$. Thus, we have obtained optimal $$$ x_i $$$. We still need to understand why $$$ p_s \geq 0 $$$. Suppose this is not the case; then, according to our estimates, $$$ x_s \geq 3 $$$. But if we increase $$$ s $$$ by $$$ 1 $$$, this estimate will decrease to $$$ x_s \geq 2 $$$, meaning we have no reason to consider this $$$ s $$$. If we cannot increase $$$ s $$$ by $$$ 1 $$$, it means that $$$ s = f $$$. Then for all $$$ i $$$, we have the estimate $$$ x_i \geq 2 $$$. But then we can simply traverse all segments from right to left and then from left to right, resulting in all $$$ x_i = 2 $$$. The case $$$ s \leq f $$$ has been analyzed. If $$$ s > f $$$, we simply need to reverse the array $$$ a_i $$$ and transition to the case $$$ s < f $$$.
Let's try to better understand what we have actually done by removing the constraints on the starting and ending positions of the dump truck. Let's look at the array $$$ x_i $$$. Initially, it contains $$$ 1 $$$ and $$$ 3 $$$; we can replace some prefix and suffix with $$$ 2 $$$. The answer to the problem is the sum of the resulting array. First, let's understand how to recalculate $$$ 1 $$$ and $$$ 3 $$$. We will sort the queries by $$$ p_{l-1} $$$ (assuming $$$ p_0 = 0 $$$). Let's consider the segment $$$ a_l, a_{l+1}, \ldots, a_r $$$. Its prefix sums are $$$ p_l - p_{l-1}, p_{l+1} - p_{l-1}, \ldots, p_r - p_{l-1} $$$. Notice that as $$$ p_{l-1} $$$ increases, the values $$$ p_i - p_{l-1} $$$ will decrease. Therefore, if we consider the queries in increasing order of $$$ p_{l-1} $$$, initially $$$ x_i = 1 $$$ for any $$$ i $$$, and then they gradually become $$$ x_i = 3 $$$ (when $$$ p_i $$$ becomes less than $$$ p_{l-1} $$$). We need to come up with a structure that can efficiently find the optimal replacement over a segment. We can simply use a Segment Tree, where each node will store $$$ 5 $$$ values — the sum over the segment without replacements; the sum over the segment if everything is replaced; the sum over the segment if the prefix is optimally replaced; the sum over the segment if the suffix is optimally replaced; and the sum over the segment if both the prefix and suffix are optimally replaced. It is not difficult to figure out how to combine $$$ 2 $$$ segments (this problem is very similar to the well-known problem of finding the maximum subarray of ones in a binary array). To solve the problem, we just need to make replacements of $$$ 1 $$$ with $$$ 3 $$$ at a point and make a query over the segment in this Segment Tree. This solution needs to be run $$$ 2 $$$ times, once for the original array $$$ a_i $$$ and once for its reversed version. The answer to the query is the minimum of the two obtained results.
The complexity of the solution is $$$ O((n + q) \log(n)) $$$ time and $$$ O(n + q) $$$ space.