绿博的帽子
Time Limit: 1000 ms
Memory Limit: 65536 KiB
Problem Description
众所周知绿博有很多绿色的帽子,就像下面这样。
有一天绿博顶着许多绿帽子回家,但是路上掉了许多绿帽子。
可以将绿博回家的路程当成一个一维数轴,出发点为 1,终点为 n 。已知绿博在每个整数点 i 会掉落 ai 顶绿帽子,现在绿博很好奇,他在一段路程 [l, r] 中总共掉了多少顶绿帽子。
Input
包含多组测试数据,第一行先输入一个正整数 T (1 <= T <= 10),代表 T 组测试数据。
每组数据第一行输入一个正整数 n (1 <= n <= 100000),代表终点。
第二行输入 n 个以空格隔开的非负整数 ai (1 <= ai <= 100),表示在每个位置掉落的绿帽子的数量。
第三行输入一个非负整数 q (0 <= q <= 100000),表示绿博有 q 次询问。
接下来有 q 行,每次输入以空格隔开的两个正整数 l 、 r (1 <= l <= r <= n),代表绿博询问区间 [l, r] 中总共掉落了多少个绿帽子。
Output
对于每组数据,输出 q 行,每行输出一个非负整数,代表绿博在所询问的区间掉落的绿帽总数。
Sample Input
1 5 1 2 3 4 5 3 1 2 3 3 4 5
Sample Output
3 3 9
Hint
Source
Fish