2006 - 英単語暗記中のKamba君

問題

Pandora高校の生徒であるKamba君は、英単語テストに備えて、英単語を猛勉強しています。Kamba君は $N$ 日に渡って単語を暗記し、$i$ 日目に $A_i$ 個の単語を覚えました。そこで、Kamba君が英単語を勉強した日数 $N$, Kamba君が新たに覚えた英単語数 $A$ を $N$ 個、質問が $Q$ 個与えられます。

・与えられる質問について 質問の内容は、「 $X$ 日目から $Y$ 日目までに覚えた英単語数を答えてください。」です。
質問のたびに、 $X$ と $Y$ は必ず与えられ、必ず　$X$ は $Y$ 以下です。

入力

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

$N$
$A_1$ $A_2$ $...$ $A_N$
$Q$
$X_1$ $Y_1$
$X_2$ $Y_2$
$:$
$:$
$X_Q$ $Y_Q$

まず、整数 $N$ が与えられ、その後 $A_i$ が $N$ 個スペース区切りで与えられる。
また、整数 $Q$ が与えられ、その後空白区切りで $X_i$ $Y_i$ が $Q$ 個だけ改行区切りで与えられる。

出力

出力の最後に改行を入れること。

制約

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

• $0 \leq N \leq 7.4 \times 10^{5}$
• $0 \leq Q \leq 7.4 \times 10^{5}$
• $1 \leq X, Y \leq N$
• $X \leq Y$

入出力例

入力例1

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

出力例1

12
12
20

入力例2

5
2 4 6 8 10
3
1 3
2 4
3 5

出力例2

12
18
24