题目描述

程猴最近刚学习了加法运算，码猴为了检测程猴的学习效果，给程猴n个数，然后会询问码猴q次，每次询问会给出两个数$a_i,b_i$，码猴需要计算出从第$a_i$个数到第$b_i$个数的和。

输入格式

第一行输入一个n。 第二行输入n个整数。 第三行输入一个q，表示q次询问。 接下来q行，每行两个整数$a_i,b_i$。

输出格式

输出q行，每行一个整数，表示每次询问的第$a_i$个到第$b_i$个数的和。

样例 #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

数据范围

$1 \leq n，q \leq 10^6$

$1 \leq a_i \leq b_i \leq 10^5$