绿博的帽子

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