题目描述

给定一个长度为 N（1 ≤ N ≤ 1000）的整数数组，数组中每个元素的初始值由输入指定。现需进行 Q 次（1 ≤ Q ≤ 1000）区间和查询，每次查询要求计算数组的某段连续区间 [L, R] 内所有元素的和。请输出每次查询的结果。

输入格式

输入共分为三部分：

1. ​​第一行​​：一个整数 N，表示数组的长度。
2. ​​第二行​​：包含 N 个整数，用空格分隔，表示数组的初始元素值（每个元素为整数，范围在 [-1e3, 1e3] 内）。
3. ​​第三行​​：一个整数 Q，表示查询次数。
4. ​​接下来 Q 行​​：每行包含两个整数 L 和 R（1 ≤ L ≤ R ≤ N），表示查询的区间范围。

​​注意​​：

• 数组下标从 1 开始（即区间 [1, N]）。

输出格式

输出共 Q 行，每行一个整数，表示对应查询的区间和。若查询区间为空（即 L > R，但输入保证 1 ≤ L ≤ R ≤ N），则输出 0。

样例

输入样例

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

15
5
9

样例解释

1. 初始数组为 [1, 2, 3, 4, 5]。
2. 第一次查询区间 [1, 5] 的和为 1 + 2 + 3 + 4 + 5 = 15。
3. 第二次查询区间 [2, 3] 的和为 2 + 3 = 5。
4. 第三次查询区间 [4, 5] 的和为 4 + 5 = 9。

数据范围

• N 和 Q 的最大值均为 1000。
• 数组元素的值范围为 [-1e3, 1e3]。