题目描述

对于一个有 $n$ 个元素的数组进行 $k$ 次区间求和。

输入格式

第一行：一个正整数 $n$； 第二行：$n$ 个正整数，表示数组中的 $n$ 个元素，每个整数不超过 $10000$，数值之间用一个空格分隔； 第三行：一个正整数 $k$，表示进行 $k$ 次区间求和； 接下来 $k$ 行：每行两个整数 $l$ 和 $r$，表示计算第 $l$ 个数组元素到第 $r$ 个数组元素的和，包括第 $l$ 个和第 $r$ 个。

输出格式

共 $k$ 行，每行对应一次求和的结果。

样例

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

6
15
40

数据范围

• 对于 $100\%$ 的数据，$1≤l≤r≤n$；
• 对于 $50\%$ 的数据，$1≤n,k≤1000$；
• 对于 $100\%$ 的数据，$1≤n,k≤100000$；