题目描述

对于一个有$\red{N}$（$\red{N<1000}$）个元素的数组进行$\red{K}$（$\red{K<2100}$）次区间求和。

输入格式

第一行: 一个正整数$\red{N}$

第二行: $\red{N}$个正整数，表示数组中的$\red{N}$个元素，每个整数不超过$\red{10000}$，数值之间用一个空格分隔。

第三行: 一个正整数$\red{K}$，表示进行$\red{K}$次区间求和。

接下来K行每行两个整数$\red{i}$和$\red{j}$，表示计算第i个数组元素到第j个数组元素的和，包括第i个和第j个。

输出格式

共K行，每行对应一次求和的结果。

样例

输入数据

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

输出数据

6
15
40