A06 - How Many Guests? Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

遊園地「ALGO-RESORT」では N 日間にわたるイベントが開催され、 i 日目 (1 \leq i \leq N) には A_i 人が来場しました。

以下の合計 Q 個の質問に答えるプログラムを作成してください。

  • 1 個目の質問：L_1 日目から R_1 日目までの合計来場者数は？
  • 2 個目の質問：L_2 日目から R_2 日目までの合計来場者数は？
  • :
  • Q 個目の質問：L_Q 日目から R_Q 日目までの合計来場者数は？

制約

  • 1 \le N,Q \le 10^5
  • 1 \le A_i \le 10000
  • 1 \le L_i \le R_i \le N
  • 入力はすべて整数

入力

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

N Q
A_1 A_2 \cdots A_N
L_1 R_1
L_2 R_2
 :
L_Q R_Q

出力

全体で Q 行出力してください。

i 行目 (1 \leq i \leq Q) には、i 個目の質問への答えを整数で出力してください。

入力例 1

10 5
8 6 9 1 2 1 10 100 1000 10000
2 3
1 4
3 9
6 8
1 10

出力例 1

15
24
1123
111
11137

この入力には 5 個の質問が含まれています。

  • 1 個目の質問は 2 日目から 3 日目までの合計来場者数を尋ねるもので、これに対する答えは 6+9=15 です。
  • 2 個目の質問は 1 日目から 4 日目までの合計来場者数を尋ねるもので、これに対する答えは 8+6+9+1=24 です。