1118. SLF 的最终之战

SLF 是个 FPS 游戏高手,这天他终于迎来了最终之战,他来到了 BOSS 关,但 BOSS 面前有 N 个房间,每个房间都有若干个怪物。BOSS 会进行 T 次防御,每次它会在 N 个房间中选出一个区间 [L,R] 作为自己的一次防御,SLF 攻破这次防御后,每个房间的怪物又会重新复活,即你可以认为每次防御都是互不影响的。SLF 对自己的枪法非常自信,他确信自己杀一个怪物只需要一发子弹,现在 SLF 想要知道对于每一次的防御他最少需要多少子弹。

输入

第一行给出一个整数 N \ (1 \leq N \leq 10^4),代表共有 N 个房间。

第二行给出 N 个整数,代表每个房间的怪物数量 X(1 \leq X \leq 100)

第三行给出一个整数 T \ (1 \leq T \leq 10^5),代表 BOSS 设置了 T 次防御。

接下来有 T 行,每行给出两个整数 L,R \ (1 \leq L \leq R \leq N),代表 BOSS 给出的防御区间。

输出

输出共 T 行,每行一个非负整数,代表 SLF 对于 BOSS 的每一次防御需要的最少的子弹数。

样例

标准输入 复制文本
5
1 2 3 4 5
2
1 5
1 3
标准输出 复制文本
15
6

提示

BOSS 第一次设置的防御区间为 [1,5],因此怪物数量为 1+2+3+4+5=15

第二次防御区间为 [1,3],因此怪物数量为 1+2+3=6

来源

2018 软件学院蓝桥杯热身赛 (For 18SEer only)

单点时限 1 秒
内存限制 128 MB
提交 185
通过 118