题目描述

给定一个长度为 $n$ 的数列 $a_1,a_2,\cdots,a_n$。同时有 $q$ 次查询操作，每次查询操作给出两个下标 $l$ 和 $r$，保证 $l\leq r$，你需要求出 $a_l+a_{l+1}+\cdots+a_r$ 的和，作为这一组查询的输出。

输入格式

第一行输入一个数字 $n$

第二行输入 $n$ 个空格隔开的数字 $a_1,a_2,\cdots,a_n$

第三行输入一个数字 $q$

接下来 $q$ 行每行输入两个空格隔开的数字代表 $l,r$

输出格式

输出一共输出 $q$ 行，每一行输出一个整数，代表每一次查询的答案。

4
4 3 2 1
2
1 4
2 3

10
5

提示

样例解释

第一个查询是求 $a_1+a_2+a_3+a_4=10$

第二个查询时求 $a_2+a_3=5$

对于 $100\%$ 的数据：$1\leq n,q≤1000,1\leq a_i\leq 10^9$。