より高速な範囲クエリ
整数が
n 個入っている配列 a が与えられており、q 個のクエリに回答する必要があります。すべてのクエリは、「インデックス [l; r]（両端含む）で区切られた配列 a の要素の合計は何か？」という形式で、インデックスは 0 から始まります。今回は、クエリの数や配列のサイズが前よりもはるかに大きくなっています。これらのクエリに素早く回答する方法を考えてみましょう。入力
入力の最初の行には、配列の要素数
n が 1 つ与えられます（1 ≤ n ≤ ）。次の行には、配列を構成する n 個の整数が空白区切りで与えられます（）。続く行には、クエリの数
q が 1 つ与えられます（1 ≤ q ≤ ）。その後の q 行には、 という形式でクエリが与えられます（）。出力
プログラムは合計で
q 行を出力し、それぞれの行にクエリ （両端含む）で区切られた配列 a の要素の合計値を出力してください。例
入力 | 出力 |
8
1 2 3 4 5 6 7 8
3
0 4
5 6
5 7 | 15
13
21 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 25 MB