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

Input

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

Output

14
17
21
13

Example 2

Input

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

Output

53
60
24
28