题目描述

李荣轩是个不折不扣的汉堡狂热爱好者，他有一个宏伟的梦想：在一天之内品尝完整个城市最受欢迎的 $n$ 家汉堡店的招牌汉堡。为了完成这个史诗级的“汉堡马拉松挑战”，李荣轩提前做好了详尽的行程规划。他从自家出发，驱车依次前往各家汉堡店。为了更精确地控制时间，他详细记录了每一段行驶路程所花费的时间。

在李荣轩的行程表上，他将整个旅程划分成了 $n$ 段路程，其中：

• 第一段路程是从家到第一家汉堡店的时间；
• 之后的第 $i$ 段路程（$i \ge 2$）则代表从第 $i-1$ 家汉堡店前往第 $i$ 家汉堡店所花费的时间。

在挑战结束后，李荣轩意犹未尽，时常回顾这次难忘的经历。为了更深入地分析自己的行程效率，他决定进行一系列的时间统计查询。每一次查询，他会指定一个起点路段编号 $l$ 和一个终点路段编号 $r$，想要知道从第 $l$ 段路程开始，到第 $r$ 段路程结束（包含两端），这连续 $r-l+1$ 段路程的总行驶时间是多少。

例如，若行程表记录的时间为 $[1, 2, 3, 4, 5]$，查询 $l=2, r=4$，则总时间应为 $2 + 3 + 4 = 9$。

李荣轩计划进行 $m$ 次这样的查询，并且希望尽快得到结果。由于数据量较大，简单的累加方法可能效率过低。请你设计一个高效的程序，帮助李荣轩快速响应每一次查询。

输入格式

• 第一行包含一个整数 $n$（$1 \le n \le 10^5$），表示李荣轩行程中的总路段数。
• 第二行包含 $n$ 个用空格分隔的整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 1000$），其中 $a_i$ 表示第 $i$ 段路程的行驶时间。
• 第三行包含一个整数 $m$（$1 \le m \le 10^5$），表示李荣轩想要进行的查询次数。
• 接下来的 $m$ 行，每行包含两个整数 $l$ 和 $r$（$1 \le l \le r \le n$），表示一次查询的起点路段编号和终点路段编号。

输出格式

• 输出共 $m$ 行，每行一个整数，表示对应查询的总行驶时间。

输入输出样例

5
1 2 3 4 5
3
1 3
2 5
1 5

6
14
15

10
10 20 30 40 50 60 70 80 90 100
4
1 10
3 7
2 4
8 9

550
250
90
170

样例解释

样例1 解释

• 第一次查询 $l=1, r=3$，总时间为 $1 + 2 + 3 = 6$。
• 第二次查询 $l=2, r=5$，总时间为 $2 + 3 + 4 + 5 = 14$。
• 第三次查询 $l=1, r=5$，总时间为 $1 + 2 + 3 + 4 + 5 = 15$。

样例2 解释

• 第一次查询 $l=1, r=10$，总时间为所有路段时间之和 $10 + 20 + \dots + 100 = 550$。
• 第二次查询 $l=3, r=7$，总时间为 $30 + 40 + 50 + 60 + 70 = 250$。
• 第三次查询 $l=2, r=4$，总时间为 $20 + 30 + 40 = 90$。
• 第四次查询 $l=8, r=9$，总时间为 $80 + 90 = 170$。