题目附件

附件与本题使用相同的访问权限。

暂无附件。

#2. 最优训练

最优训练

最优训练

英文名:Turtle vs. Rabbit Race: Optimal Trainings

题目描述

Isaac 开始训练。一共有 nn 条跑道,第 ii 条跑道(1≤i≤n1 \le i \le n)由 aia_i 段长度相等的路段组成。

给定一个整数 uu(1≤u≤1091 \le u \le 10^9),每完成一段路,Isaac 的能力会增加一个特定的值:

  • 完成第 11 段,能力增加 uu;
  • 完成第 22 段,能力增加 u−1u-1;
  • 完成第 33 段,能力增加 u−2u-2;
  • ……
  • 完成第 kk 段(k≥1k \ge 1),能力增加 u+1−ku+1-k。(该值可以为负数,即多完成一段反而会降低能力。)

另外给定一个整数 ll。你需要选择一个整数 rr,满足 l≤r≤nl \le r \le n,Isaac 会跑完第 l,l+1,…,rl, l+1, \dots, r 条跑道的每一段(总共 ∑i=lrai=al+al+1+⋯+ar\sum_{i=l}^{r} a_i = a_l + a_{l+1} + \dots + a_r 段)。

问题:选择怎样的 rr,才能使 Isaac 能力的增加量最大?

如果有多个 rr 都能使增加量最大,输出最小的 rr。

为了增加难度,你需要对 qq 组不同的 (l,u)(l, u) 回答上述问题。

输入格式

第一行一个整数 tt(1≤t≤1041 \le t \le 10^4),表示测试数据组数。

接下来依次给出每组数据:

  • 第一行一个整数 nn(1≤n≤1051 \le n \le 10^5)。
  • 第二行 nn 个整数 a1,a2,…,ana_1, a_2, \dots, a_n(1≤ai≤1041 \le a_i \le 10^4)。
  • 第三行一个整数 qq(1≤q≤1051 \le q \le 10^5)。
  • 接下来 qq 行,每行两个整数 l,ul, u(1≤l≤n1 \le l \le n,1≤u≤1091 \le u \le 10^9)。

输出格式

对于每组测试数据,输出一行 qq 个整数:第 ii 个整数表示第 ii 个询问的最优 rr。若答案不唯一,输出其中最小的 rr。

样例

样例 1

输入

5
6
3 1 4 1 5 9
3
1 8
2 7
5 9
1
10
1
1 1
9
5 10 9 6 8 3 10 7 3
5
8 56
1 12
9 3
1 27
5 45
5
7 9 2 5 2
10
1 37
2 9
3 33
4 32
4 15
2 2
4 2
2 19
3 7
2 7
10
9 1 6 7 6 3 10 7 3 10
5
10 43
3 23
9 3
6 8
5 14

输出

3 4 5
1
9 2 9 4 9
5 2 5 5 5 2 4 5 4 2
10 6 9 7 7

说明

针对第一组数据(a=[3,1,4,1,5,9]a = [3,1,4,1,5,9]):

  • 询问 (l,u)=(1,8)(l,u)=(1,8):选 r=3r=3 时共跑 3+1+4=83+1+4=8 段,收益为 8+7+6+5+4+3+2+1=368+7+6+5+4+3+2+1=36;选 r=4r=4 时共跑 99 段,收益为 8+7+6+5+4+3+2+1+0=368+7+6+5+4+3+2+1+0=36。两者并列最优,取较小的 r=3r=3。
  • 询问 (l,u)=(2,7)(l,u)=(2,7):选 r=4r=4 时共跑 1+4+1=61+4+1=6 段,收益为 7+6+5+4+3+2=277+6+5+4+3+2=27,最优。
  • 询问 (l,u)=(5,9)(l,u)=(5,9):选 r=5r=5 时共跑 55 段,收益为 9+8+7+6+5=359+8+7+6+5=35;选 r=6r=6 时共跑 1414 段,收益同样为 3535。取较小的 r=5r=5。

因此第一组数据输出 3 4 5。

样例 2

输入

1
5
2 3 1 4 2
4
1 5
2 3
3 1
4 2

输出

2 2 3 4

说明

共有 55 条跑道,a=[2,3,1,4,2]a=[2,3,1,4,2],前缀和 P=[0,2,5,6,10,12]P=[0,2,5,6,10,12]。

  • 询问 (1,5)(1,5):收益在 S=5S=5 与 S=6S=6 处并列最大,对应的最小下标为 r=2r=2(S=5S=5)。
  • 询问 (2,3)(2,3):S=3S=3(r=2r=2)与 S=4S=4(r=3r=3)收益并列最大,取 r=2r=2。
  • 询问 (3,1)(3,1):l=3l=3,u=1u=1,最优为 r=3r=3。
  • 询问 (4,2)(4,2):l=4l=4,u=2u=2,最优为 r=4r=4。

因此输出 2 2 3 4。

数据范围与约定

对全部测试点:1≤t≤1041 \le t \le 10^4,1≤n≤1051 \le n \le 10^5,1≤q≤1051 \le q \le 10^5,∑n≤2×105\sum n \le 2 \times 10^5,∑q≤2×105\sum q \le 2 \times 10^5,1≤ai≤1041 \le a_i \le 10^4,1≤l≤n1 \le l \le n,1≤u≤1091 \le u \le 10^9。

子任务 分值 约束
1 30 n,q≤2×103n, q \le 2 \times 10^3
2 70 无额外限制