The Logging Company has a long line of ~N~ ~(1 \le N \le 1\,000\,000)~ trees numbered from ~0~ to ~N-1~. Each tree ~i~ has a mass ~m_i~ ~(0 \le m_i \le 2000)~. The Company wants to cut some of the trees, so they hired you to calculate the mass of all the wood they would get from cutting all the trees between positions ~a~ and ~b~ inclusive ~(0 \le a, b < N)~. In particular, they want you to answer ~Q~ ~(1 \le Q \le 1\,000\,000)~ such queries.

Input Specification

• First line: ~N~.
• Lines ~2~ to ~N+1~: line ~i+2~ is the mass of tree ~i~, ~m_i~.
• The line ~N+2~ will contain the integer ~Q~, the number of queries the logging company wants answered.
• The next ~Q~ lines will contain the integers ~a~ and ~b~.

Output Specification

For each query, print the total mass of the trees at position ~i~ such that ~a \le i \le b~.

Scoring

• For 30% of the points, ~N, Q \le 1\,000~.
• For 50% of the points, ~N, Q \le 10\,000~.
• For the rest, ~N, Q \le 1\,000\,000~.

Sample Input

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

Sample Output

15
9
3