题目描述

阿者和阿波是红河哈尼梯田边长大的好朋友。阿者最近在学加法，阿波为了考考他，决定用哈尼村寨里的红米（红河特产）来出题。

村里有 n 个粮仓，从1开始按顺序编号，第 i 个粮仓里存有 a[i] 袋红米。

阿波会进行 q 次提问，每次提问给出两个仓编号 L 和 R，阿者需要回答：从第 L 个粮仓到第 R 个粮仓（包括两端）一共有多少袋红米？

虽然阿者很聪明，但粮仓最多可达 $10^6$ 个，他算不过来，请你帮忙写程序解答。

输入格式

第一行输入一个整数 n，表示粮仓的数量。

第二行输入 n 个整数，表示每个粮仓的红米袋数。

第三行输入一个整数 q，表示提问的次数。

接下来 q 行，每行两个整数 L, R，表示询问从第 L 个粮仓到第 R 个粮仓的红米总数。

输出格式

输出 q 行，每行一个整数，表示对应询问的红米总袋数。

样例 #1

样例输入 #1

6
2 5 3 1 2 1
5
2 3
1 4
3 6
4 4
3 5

样例输出 #1

8
11
7
1
6

数据范围

• 对于 20% 的数据，$1 \le n,q \le 10^2$。
• 对于 40% 的数据，$1 \le n,q \le 10^3$。
• 对于 100% 的数据，$1 \le n,q \le 10^6$。
• 每个粮仓的红米袋数是不超过 $10^6$ 的非负整数。