Codeforces Round 980 (Div. 1) |
---|
Finished |
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.
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$$$.
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.
51 1-1791 15 3-2 2 -1 3 -12 41 51 37 11 1 1 -4 1 1 11 77 22 -2 2 -2 1 2 -11 72 74 41000000000 1000000000 999999999 -10000000002 43 42 31 3
-1 2 5 -1 8 6 6 2 -1 1 2
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:
Name |
---|