题目描述

小高保存了一份睡眠日志。该日志由一个长度为奇数的序列 $A=(A_1(=0), A_2,\ldots,A_N)$ 表示，其中奇数位元素表示他起床的时间，偶数位元素表示他上床睡觉的时间。更具体地说，在开始记录睡眠日志后，他有以下睡眠时段：

• 对于每个整数 $i$ 满足 $1\leq i\leq\dfrac{N-1}2$，他在开始记录睡眠日志后的第 $A_{2i}$ 分钟准确地入睡，并在第 $A_{2i+1}$ 分钟准确地醒来。
• 他没有在任何其他时间入睡或醒来。

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

在开始记录睡眠日志后的第 $l_i$ 分钟到第 $r_i$ 分钟期间，小高总共睡了多少分钟？

输入格式

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

$N$

$A_1$ $A_2$ $\ldots$ $A_N$

$Q$

$l_1$ $r_1$

$l_2$ $r_2$

$\vdots$

$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

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

样例1解释

小高的睡眠情况如下图所示。

每个问题的答案如下：

• 在开始记录睡眠日志后的第480分钟到第1920分钟期间，小高在3个睡眠时段中睡觉：从480分钟到720分钟，从1320分钟到1440分钟，以及从1800分钟到1920分钟。总睡眠时间为 $240+120+120=480$ 分钟。
• 在开始记录睡眠日志后的第720分钟到第1200分钟期间，小高没有睡觉。总睡眠时间为 $0$ 分钟。
• 在开始记录睡眠日志后的第0分钟到第2160分钟期间，小高在3个睡眠时段中睡觉：从240分钟到720分钟，从1320分钟到1440分钟，以及从1800分钟到2160分钟。总睡眠时间为 $480+120+360=960$ 分钟。

因此，输出的三行应该包含 $480$、$0$ 和 $960$。

数据范围

• $3\leq N<2\times10^5$, $N$ 是奇数。
• $0=A_1< A_2<\cdots< A_N\leq10^9$
• $1\leq Q\leq2\times10^5$
• $0\leq l_i\leq r_i\leq A_N\ (1\leq i\leq Q)$
• 所有输入值都是整数。

来源

• AtCoder ABC305D