P14126 [HackerEarth] Maggu is very serious about his work. He is so bossy that everyone fears him.
普及
题目描述

Maggu is very serious about his work. He is so bossy that everyone fears him.

One day he gave his assistant N records with a number r[i] written on each of them. He wanted his assistant to quickly fulfill his Q queries of sum of numbers written on the ith to jth records.
One query i j represents r[i] + r[i+1] + ..... + r[j-1] + r[j].
His assistant is very poor in calculations & fears that Maggu will fire her at failure, so she needs your programming skills to save her job.

INPUT:

First line will contain the number of records N.

Next line contains N integers r[i] denoting the number written on ith record.

Next line will contain the number of queries Q proposed by Maggu.

Next Q lines will contain a query of the form "i j"

OUTPUT:

For each query "i j", output the sum of numbers written on ith record to jth record on separate lines.

CONSTRAINTS:

1 ≤ N ≤ 10^6

1 ≤ r[i] ≤ 10^9

1 ≤ Q ≤ 10^6

1 ≤ i ≤ j ≤ N

SAMPLE INPUT
10
6 8 9 2 3 4 6 2 1 63
5
3 7
1 4
2 9
5 6
4 4

SAMPLE OUTPUT
24
25
35
7
2

输入格式

见题面

输出格式

见题面

样例输入
100 4001 9579 4744 5444 4018 5135 6784 9875 9512 2435 5350 2957 8597 812 7045 2973 1193 3632 8186 9125 4309 9544 1275 6753 3032 2694 5208 4767 7109 9937 1739 1110 9515 2835 2905 9885 7969 9689 9759 3833 8475 5109 6789 7072 2272 185 44 3464 168 4581 8941 828 4124 6567 7580 3508 5612 2787 4626 2721 9076 2717 3830 8590 5551 6734 4826 3519 2774 4585 3703 1249 6045 492 8320 8316 7028 4715 8132 7196 5647 7072 4375 6122 9990 1955 9629 5601 1093 607 8321 168 3323 2150 5110 8873 5236 9935 8743 8009 100 1 94 3 98 4 95 9 99 4 98 3 93 1 95 3 98 3 93 2 93 5 99 6 99 1 93 1 96 2 94 6 99 1 92 2 100 2 95 5 100 1 100 3 93 5 95 4 100 9 99 1 99 8 98 6 96 9 99 7 98 5 95 7 98 4 94 10 100 5 95 2 94 8 100 2 100 3 99 2 93 3 98 2 96 7 100 6 96 3 97 2 99 4 96 6 99 7 99 2 97 6 97 7 97 6 99 1 93 6 99 1 94 4 98 6 98 2 95 3 94 7 99 1 92 8 98 2 99 4 95 5 100 6 97 9 100 1 96 2 94 4 100 3 93 3 100 5 100 4 99 10 100 2 96 2 94 9 99 5 95 6 100 2 97 3 93 2 93 1 94 1 99 3 100 2 93 2 92 7 98 9 100 3 94 7 98 1 97 2 96 3 99 1 99 3 98 3 100 2 100
样例输出
2 1