问题描述

给定一个长度为 n 的数组 a，有 q 次询问，每次询问数组 a 在区间 [l, r] 的和。

格式

输入

第一行一个整数 n，($1 ≤ n ≤ 10^5$) 第二行 n 个整数表示数组 a，($-10^9 ≤ ai ≤ 10^9$) 第三行一个整数 q，($1 ≤ q ≤ 10^5$) 接下来 q 行，每行两个整数 li, ri，(1 ≤ li ≤ ri ≤ n)

输出

每一行对应每一个样例，输出一个整数表示答案。

样例

5
1 2 3 4 5
2
1 3
2 5

6
14

提示

数据范围、额外说明、样例说明等等