Scavenging in Fountains

Jerry desperately needs money. At the bottom of a pool lies a line of coins.

You are given an array $a_1, \dots, a_n$, where $a_i$ is the value of the $i$-th coin. Jerry asks you $q$ questions: if he scoops up all the coins between the $l$-th and $r$-th coins (inclusive), what is the total value of the coins he scoops up?

Input

The first line contains the integer $n$, the number of coins in the fountain.

The second line contains $n$ integers, $a_1, \dots, a_n$, where $a_i$ is the value of the $i$-th coin.

The third line contains the integer $q$, the number of questions Jerry will ask.

The following $q$ lines each contain two integers $l$ and $r$, asking for the total value of the coins from the $l$-th coin through the $r$-th coin. The queries are 1-indexed.

Output

For each question Jerry asks, output a line containing the answer.

Constraints

• $1 \le l \le r \le n \le 10^6$
• $1 \le a_i \le 10^9$
• $1 \le q \le 10^6$

Example 1

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

14
17
21
13

Example 2

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

53
60
24
28