题目描述

沈阳是一个充满历史与文化底蕴的城市，吸引了大量的游客前来观光。津津、菲菲和皮皮计划统计并分析各个景点的游客流量数据。他们获得了一个数列 $a_1,a_2,\ldots,a_n$，其中 $a_n$ 表示第 $n$ 个景点的游客流量。此外，他们还得到了 $m$ 个区间 $[l_i, r_i]$，每个区间代表一个特定的时间段。现在，请你帮助他们编写一个程序，计算这些区间的总游客流量。

输入格式

• 第一行：一个正整数 $n$，表示景点的数量
• 第二行：$n$ 个正整数 $a_1,a_2,\ldots,a_n$，表示每个景点的游客流量
• 第三行：一个正整数 $m$，表示区间的数量
• 接下来 $m$ 行：每行两个正整数 $l_i,r_i$，表示一个时间段，满足 $1 \le l_i \le r_i \le n$

输出格式

输出 $m$ 个整数，分别表示每个时间段的景点总游客流量

样例

输入样例1

5
100 150 200 180 250
3
1 3
2 4
1 4

输出样例1

450
530
630