Problem Description

Given a sequence $a_1, a_2, \cdots, a_n$ consisting of $n$ positive integers and $m$ intervals $[l_i, r_i]$, find the sum of elements in each of the $m$ intervals.

Input Format

The first line contains a positive integer $n$, representing the length of the sequence.

The second line contains $n$ positive integers $a_1, a_2, \cdots, a_n$.

The third line contains a positive integer $m$, representing the number of intervals.

The next $m$ lines each contain two positive integers $l_i, r_i$, satisfying $1 \le l_i \le r_i \le n$.

Output Format

Output $m$ lines. The $i$-th line contains a positive integer, representing the answer to the $i$-th query.

4
4 3 2 1
2
1 4
2 3

10
5

Hint

Sample Explanation

The sum of the $1$st to the $4$th numbers is $10$. The sum of the $2$nd to the $3$rd numbers is $5$.

Constraints

For $50\%$ of the testdata: $n, m \le 1000$.

For $100\%$ of the testdata: $1 \le n, m \le 10^5$, $1 \le a_i \le 10^4$.

Translated by ChatGPT 5