No.10 鉄道

時間制限:$2.0sec$ / メモリ制限:$256MB$

問題文

kotamanegi君はよく電車に乗って移動します。

彼が使う鉄道会社には駅が$n$駅あり、駅$1$と駅$2$、駅$2$と駅$3$…駅$n-1$と駅$n$が繋がっています。

駅間の距離$x$が与えられるので、$q$組の駅$a$と駅$b$の距離を求めてください。

制約

• $2 ≦ n ≦ 100000$
• $1 ≦ x ≦ 10000$
• $1 ≦ q ≦ 100000$
• $1 ≦ a < b ≦ n$
• $xi$は駅$i$と駅$i+1$の距離を表す。

入力形式

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

n
x1 x2 x3 … x(n-1)
q
a1 b1
a2 b2
……
aq bq

出力

合計で$q$行、それぞれの駅間について、距離を出力してください。

改行を忘れないこと。

入出力例

2
3
1
1 2

3

駅$1$と駅$2$の距離は$3$です。

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

5
10
45

• 駅$2$と駅$4$の距離は$2+3=5$です。
• 駅$1$と駅$5$の距離は$1+2+3+4=10$です。
• 駅$1$と駅$10$の距離は$1+2+3+4+5+6+7+8+9=45$です。