在一座丘陵地貌的沙漠城市,市政府决定购买一辆自卸车来平整路面。道路分为 $$$n$$$ 段,从左到右编号为 $$$1$$$ 到 $$$n$$$。第 $$$i$$$ 部分的表面高度等于 $$$a_i$$$。如果第$$$i$$$路段的高度大于$$$0$$$,则自卸车必须从第$$$i$$$路段取沙,如果第$$$i$$$路段的高度小于$$$0$$$,则自卸车必须用沙子填充第$$$i$$$路段的坑。保证初始高度不等于$$$0$$$。
当自卸车处于第 $$$i$$$ 路段时,它可以带走 $$$x$$$ 单位的沙子,此时第 $$$i$$$ 路段的路面高度将减少 $$$x$$$,或者填充 $$$x$$$ 单位的沙子(前提是其当前路段中至少有 $$$x$$$ 单位的沙子)床),在这种情况下,第 $$$i$$$ 路段的路面高度将增加 $$$x$$$。
自卸车可以从任何路段开始行驶。移动到左侧或右侧的相邻部分需要$$$1$$$分钟,装卸沙子的时间可以忽略不计。自卸车的容量无限大,最初是空的。
您需要找到自卸车平整沙子所需的最短时间,以使每个部分的高度等于 $$$0$$$。请注意,在完成所有移动后,自卸车的车床上可能仍留有沙子。您需要针对编号从 $$$l_i$$$ 到 $$$r_i$$$ 的段独立解决此问题。不能使用段外的沙子。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。测试用例的描述如下。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n, q \le 3 \cdot 10^5$$$) — 节数和查询数。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$-10^9 \le a_i \le 10^9$$$, $$$a_i \neq 0$$$) — 每个部分的初始高度。
以下 $$$q$$$ 行中的第 $$$i$$$ 行包含两个整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — 需要确定最短时间的段的边界。
保证所有测试用例的 $$$n$$$ 之和以及所有测试用例的 $$$q$$$ 之和不超过 $$$3 \cdot 10^5$$$。
输出
对于每个查询,输出平整 $$$[l_i, r_i]$$$ 段中的沙子所需的最短时间,如果不可能,则输出 $$$-1$$$。
示例
输入 #1
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
输出 #1
-1 2 5 -1 8 6 6 2 -1 1 2
注意
在第一个测试用例中,需要将 $$$179$$$ 单位的沙子添加到唯一的部分。然而,无处可取,所以这是不可能的。
在第二个测试用例中:
- 在第一个查询中,自卸车可以在第二个路段开始行驶。它可以容纳 $$$2$$$ 单位的沙子,之后第二部分的高度将变为 $$$0$$$。然后自卸车就可以移动到第三段。它可以在那里倒$$$1$$$单位的沙子,之后第三部分的高度将变成$$$0$$$。然后自卸车就可以移动到第四节段。在那里它可以容纳 $$$3$$$ 单位的沙子,之后第四部分的高度将变为 $$$0$$$。总共,自卸车的移动时间为 $$$2$$$ 分钟。
- 在第二个查询中,自卸车可以在第四个路段开始行驶。它可以容纳 $$$3$$$ 单位的沙子,之后第四部分的高度将变为 $$$0$$$。然后自卸车就可以移动到第五节段。它可以在那里倒$$$1$$$单位的沙子,之后第五部分的高度将变成$$$0$$$。然后自卸车可以移回第四段,然后再移至第三段。它可以在那里倒$$$1$$$单位的沙子,之后第三部分的高度将变成$$$0$$$。然后自卸车就可以移动到第二段。它可以使用 $$$2$$$ 单位的沙子。然后它可以移动到第一部分。它可以在那里倒$$$2$$$单位的沙子,之后第一部分的高度将变成$$$0$$$。总共,自卸车将花费 $$$5$$$ 分钟的移动时间。
- 在第三个查询中,自卸车将无法使每个部分的高度等于$$$0$$$。