题目描述

给定一个长度为 $n$ 的正整数序列：

以及 $m$ 个区间：

对于每个区间，请计算该区间内所有元素的和，即：

输入格式

第一行输入一个正整数 $n$，表示序列的长度。

第二行输入 $n$ 个正整数 $a_1,a_2,\ldots,a_n$，表示给定序列。

第三行输入一个正整数 $m$，表示询问区间的数量。

接下来 $m$ 行，每行输入两个正整数 $l_i$、$r_i$，表示一个询问区间。

输出格式

输出 $m$ 行。

第 $i$ 行输出一个整数，表示区间 $[l_i,r_i]$ 内所有元素的和。

样例

4
4 3 2 1
2
1 4
2 3

10
5

样例解释

第 $1$ 个询问区间为 $[1,4]$，区间和为：

第 $2$ 个询问区间为 $[2,3]$，区间和为：

数据范围

对于 $50$ 的测试数据：

$n,m \le 1000$。

对于 $100$ 的测试数据：

$1 \le n,m \le 10^5$。

$1 \le a_i \le 10^4$。

$1 \le l_i \le r_i \le n$。

来源：洛谷P8218