该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定 $n$ 个正整数组成的数列 $a_1, a_2, ..., a_n$ 和 $m$ 个区间 $[l_i, r_i]$，分别求这 $m$ 个区间的区间和。

输入格式

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

第二行包含 $n$ 个正整数 $a_1, a_2, ..., a_n$。

第三行包含一个正整数 $m$，表示区间的数量。 接下来 $m$ 行，每行包含两个正整数 $l_i, r_i$，满足 $1 ≤ l_i ≤ r_i ≤ n$。

限制

$1 ≤ n, m ≤ 10^5，1 ≤ a_i ≤ 10^4$。

输出格式

共 $m$ 行，其中第 $i$ 行包含一个正整数，表示第 $i$ 组答案的询问。

样例

4
4 3 2 1
2
1 4
2 3

10
5

样例解释

第 1 到第 4 个数加起来和为 10。 第 2 个数到第 3 个数加起来和为 5。