CF2023F Hills and Pits

在一个地势起伏的沙漠城市中，市政府计划购置一辆自卸卡车来平整道路。道路按从左到右的顺序被分为 $ n $ 段，编号为 $ 1 $ 到 $ n $。第 $ i $ 段道路的初始高度是 $ a_i $ 。如果某段道路的高度高于 $ 0 $，则需要自卸卡车从中移走部分沙子；如果低于 $ 0 $，则需要用沙子填平。所有路段在开始时的高度都不为 $ 0 $。 当卡车在第 $ i $ 段时，它可以取走 $ x $ 单位的沙子，使该段高度减少 $ x $，或者可以填入 $ x $ 单位的沙子（前提是车上至少有 $ x $ 单位沙子），使该段高度增加 $ 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 $ 行中，每行两个整数 $ l_i $ 和 $ r_i $ （$ 1 \le l_i \le r_i \le n $），表示需要寻找最短时间的区间。 保证所有测试用例中 $ n $ 的总和以及 $ q $ 的总和不超过 $ 3 \cdot 10^5 $。

对于每个查询，输出调整区间 $ [l_i, r_i] $ 的沙子高度至 $ 0 $ 所需的最短时间，如果无法完成，输出 $ -1 $。 **本翻译由 AI 自动生成**

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