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 自动生成