睡眠记录

题目描述

高桥君记录了自己的睡眠日志。 日志用一个长度为奇数的序列 $A=(A_1(=0), A_2, \ldots, A_N)$ 表示,其中奇数下标元素表示起床时间,偶数下标元素表示入睡时间。 更形式化地说,开始记录日志后,他的睡眠情况如下。

对于满足 $1 \le i \le \frac{N-1}{2}$ 的每个整数 $i$,他在开始记录后的第 $A_{2i}$ 分钟入睡,并在开始记录后的第 $A_{2i+1}$ 分钟起床。

除此之外,他没有在任何其他时间入睡或起床。

回答以下 $Q$ 个问题。 第 $i$ 个问题给出一对整数 $(l_i, r_i)$,满足 $0 \le l_i \le r_i \le A_N$。

在开始记录后第 $l_i$ 分钟到第 $r_i$ 分钟这 $r_i - l_i$ 分钟里,高桥君一共睡了多少分钟?

输入格式

输入按以下格式从标准输入给出:

N
A_1 A_2 … A_N
Q
l_1 r_1
l_2 r_2
⋮
l_Q r_Q

输出格式

输出 $Q$ 行。 第 $i$ 行应输出第 $i$ 个问题的答案(一个整数)。

样例

7
0 240 720 1320 1440 1800 2160
3
480 1920
720 1200
0 2160

480
0
960

各问题的答案如下。

在开始记录后第 $480$ 分钟到第 $1920$ 分钟之间,高桥君分别在 $480$ 分钟到 $720$ 分钟、$1320$ 分钟到 $1440$ 分钟、$1800$ 分钟到 $1920$ 分钟这 $3$ 段睡眠中睡着。总睡眠时间为 $240+120+120=480$ 分钟。

在开始记录后第 $720$ 分钟到第 $1200$ 分钟之间,高桥君没有睡着。总睡眠时间为 $0$ 分钟。

在开始记录后第 $0$ 分钟到第 $2160$ 分钟之间,高桥君分别在 $240$ 分钟到 $720$ 分钟、$1320$ 分钟到 $1440$ 分钟、$1800$ 分钟到 $2160$ 分钟这 $3$ 段睡眠中睡着。总睡眠时间为 $480+120+360=960$ 分钟。

因此,输出的三行应分别为 $480$,$0$,$960$。

21
0 20 62 192 284 310 323 324 352 374 409 452 486 512 523 594 677 814 838 946 1000
10
77 721
255 541
478 970
369 466
343 541
42 165
16 618
222 592
730 983
338 747

296
150
150
49
89
20
279
183
61
177

数据范围

• $3 \le N \lt 2 \times 10^5$
• $N$ 是奇数。
• $0 = A_1 \lt A_2 \lt \cdots \lt A_N \le 10^9$
• $1 \le Q \le 2 \times 10^5$
• $0 \le l_i \le r_i \le A_N$ $(1 \le i \le Q)$
• 所有输入值均为整数。