004 - 病気の山本くん

問題

山本くんは風邪をひいてしまいました。
そのため、一日中寝ていなくてはなりません。
しかし、全く眠れません。羊をただ数えるのも飽きました。
そこで、以下のような状況を想像することにしました。

• $N$ 個の牧場が並んでいて、$i$ $(1 \leq i \leq N)$ 番目の牧場には $A_i$ 匹の羊がいる

そして、$Q$ 回に渡って以下の値を求めることにしました。

• $L_j$ 番目から $R_j$ 番目 $(1 \leq j \leq Q)$ までにある牧場の羊の合計

この結果を $Q$ 回に渡って改行区切りで出力してください。

入力

入力は以下の形式で標準入力から与えられる。

$N$
$A_1 \ldots A_N$
$Q$
$L_1 R_1$
$\vdots$
$L_Q R_Q$

出力

$Q$ 回に渡って答えを出力せよ。各出力の末尾に改行を入れること。

制約

全ての入力ケースについて以下を満たす。

• $1 \leq N \leq 10^6$
• $0 \leq A_i \leq 10^5$
• $1 \leq Q \leq 10^5$
• $1 \leq L_j \leq R_j \leq N$
• 入力は全て整数である

部分点

• $1 \leq N,Q \leq 10^3$ を満たすケースに正解したとき、部分点として $20$ 点が与えられます。
• 追加制約のないケースに正解したとき、追加で $20$ 点が与えられ、合計で $40$ 点が与えられます。

入出力例

入力例1

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

出力例1

9
9
15

解説

$2,3,4$ 番目の牧場の羊たちの合計は $2 + 3 + 4 = 9$ です。

入力例2

1
73
3
1 1
1 1
1 1

出力例2

73
73
73