You are given an array of budget values and multiple range queries.

For each query [L, R], determine the sum of the elements between indices L and R (inclusive).

Since the number of queries can be very large, an efficient solution is required.

---

Input Format

• The first line contains an integer N, representing the number of budget entries.
• The second line contains N space-separated integers representing the budget values.
• The third line contains an integer Q, representing the number of queries.
• The fourth line contains an integer 2, representing the number of columns in the query matrix.
• The next Q lines each contain two integers L and R.

---

Output Format

Print Q lines, where the i-th line contains the sum of the elements in the range [L, R].

---

Constraints

• 1 ≤ N, Q ≤ 2 × 10^5
• -10^9 ≤ A[i] ≤ 10^9
• 0 ≤ L ≤ R < N

---

Sample Input

6
2 4 1 7 3 5
4
2
0 2
1 4
2 5
3 3

Sample Output

7
15
16
7

---

Explanation

• Query [0, 2] → 2 + 4 + 1 = 7
• Query [1, 4] → 4 + 1 + 7 + 3 = 15
• Query [2, 5] → 1 + 7 + 3 + 5 = 16
• Query [3, 3] → 7 = 7

---

Note

• Indices are 0-based.
• There are no update operations; only range sum queries.