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 的每一次防御需要的最少的子弹数。

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

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