描述

应广大同学的要求，领取红包的活动有了新的规则，更加刺激，更加有趣。

新春佳节，方块鸟要给大家发红包啦。在正月十五以前来到方块鸟的同学，都可以领取红包。领取红包的规则是这样的：

1. 在桌子上有$N$个排列好的格子，从1号到$N$号
2. 每个格子里写了一个数字
3. 领取红包时，通过点击程序上的抽奖按钮，会得到两个幸运数字$X, Y$
4. 将从X到Y的格子（含$X$号和$Y$号格子）中的数字加起来，就是可以领取的红包金额
5. 红包会在正月十六号统一以帐号积分的形式存到大家的学员积分账号中
6. 学员积分账号可以用来兑换水杯、帽子、衣服、习题册（老师亲笔签名版）等精美礼品

到了正月十六号，一共有$q$名同学参与了领取红包活动，他们分别抽到$(x_1, y_1), (x_2, y_2) , (x_3, y_3) , ..., (x_n, y_n)$。请你编写程序写出每个同学领到了多少金额。

输入输出格式

输入

第一行为一个正整数$N$，表示桌子上的格子数量 ($1 < N ≤ 100,000$)

第二行为$N$个以空格分割的数字$y_1, y_2, ..., y_n$，为格子里写的数字

第三行为一个正整数$q$，表示参与了领取红包活动的同学数量 ($1 < N ≤ 100,000$)

随后$q$行，每行两个以空格分割的正整数$x, y$，表示该同学抽到的幸运数字 （$1 ≤ X, Y ≤ N$)

输出

q行，按顺序输出每个同学领到的红包金额

样例

9
1 2 3 4 5 6 7 8 9
3
1 3
2 7
5 3

6
27
12