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

时间限制: 1 秒 / 内存限制: 256 MiB

题目描述

小明在记录睡眠日志。

睡眠日志用一个奇数长度的序列 $A=(A_1(=0), A_2, \ldots, A_N)$ 来表示，其中奇数编号的元素表示起床时刻，偶数编号的元素表示就寝时刻。

更严格地说，在开始记录睡眠日志后，小明的睡眠情况如下：

• 对于所有满足 $1 \leq i \leq \dfrac{N-1}{2}$ 的整数 $i$，高桥君在开始记录后第 $A_{2i}$ 分钟整入睡，在第 $A_{2i+1}$ 分钟整起床。
• 在其他时间，小明既没有入睡也没有起床。

请回答以下 $Q$ 个问题。

第 $i$ 个问题给出一个满足 $0 \leq l_i \leq r_i \leq A_N$ 的整数对 $(l_i, r_i)$：

• 从开始记录后第 $l_i$ 分钟整到第 $r_i$ 分钟整的 $r_i - l_i$ 分钟内，小明一共睡了多少分钟？

约束条件

• $3 \leq N < 2 \times 10^5$
• $N$ 是奇数
• $0 = A_1 < A_2 < \cdots < A_N \leq 10^9$
• $1 \leq Q \leq 2 \times 10^5$
• $0 \leq l_i \leq r_i \leq A_N$（$1 \leq i \leq Q$）
• 所有输入值均为整数

输入

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

N
A₁ A₂ … Aₙ
Q
l₁ r₁
l₂ r₂
⋮
lQ rQ

输出

输出 $Q$ 行，第 $i$ 行输出第 $i$ 个问题的答案（整数）。

样例

样例输入 1

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

样例输出 1

480
0
960

解释: 小明的睡眠情况如下：

• 第 1 个问题：480 分钟到 1920 分钟之间，小明有 3 段睡眠：480~720 分钟、1320~1440 分钟、1800~1920 分钟。总睡眠时间 = 240 + 120 + 120 = 480 分钟。
• 第 2 个问题：720 分钟到 1200 分钟之间，小明没有睡眠。总睡眠时间 = 0 分钟。
• 第 3 个问题：0 分钟到 2160 分钟之间，小明有 3 段睡眠：240~720 分钟、1320~1440 分钟、1800~2160 分钟。总睡眠时间 = 480 + 120 + 360 = 960 分钟。

样例输入 2

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

样例输出 2

296
150
150
49
89
20
279
183
61
177