#P18349. Add One 3

Add One 3

Add One 3

给定一个长度为 nn 的整数序列 a1,a2,…,ana_1,a_2,\ldots,a_n。一次操作选择一个位置 ii,令 ai←ai+1a_i\gets a_i+1。

有 qq 个询问,每个询问给出一个区间 [l,r][l,r]。求至少进行多少次操作,才能使 [l,r][l,r] 成为整个序列中唯一的最大和连续子段。如果无法实现,输出 −1-1。

连续子段由一对下标 1≤i≤j≤n1\le i\le j\le n 确定,其和为 ∑k=ijak\sum_{k=i}^j a_k。比较时还允许选择空子段,空子段的和为 00。因此,最终的区间 [l,r][l,r] 必须满足:

  • 区间和严格大于 00;
  • 区间和严格大于其他所有非空区间的和。

各个询问相互独立,操作只是假设进行,不会改变后续询问所使用的原序列。

输入格式

第一行一个整数 tt,表示测试用例数。

对于每个测试用例:

  • 第一行两个整数 n,qn,q;
  • 第二行 nn 个整数 a1,a2,…,ana_1,a_2,\ldots,a_n;
  • 接下来 qq 行,每行两个整数 l,rl,r,表示一个询问。

数据范围:

  • 1≤t≤1051\le t\le10^5;
  • 1≤n,q≤5×1051\le n,q\le5\times10^5;
  • −109≤ai≤109-10^9\le a_i\le10^9;
  • 1≤l≤r≤n1\le l\le r\le n;
  • 一个输入文件中所有 nn 的和不超过 5×1055\times10^5,所有 qq 的和也不超过 5×1055\times10^5,两个限制分别成立。

输出格式

对于每个询问输出一行一个整数,表示最少操作次数;无解时输出 −1-1。

样例输入 1

2
6 6
-1 2 -2 0 1 -1
1 1
1 2
1 3
1 4
1 5
1 6
1 1
0
1 1

样例输出 1

-1
2
-1
-1
4
5
1