分数: 450 点
问题陈述
高桥保留睡眠日志。 日志表示为奇数长度序列 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.
- 高桥睡着的总分钟数是多少 r _ i-l _ i 分钟距离 l _ i 分钟到 r _ i 启动睡眠日志后分钟?
约束
- 3\leq N\lt2\times10^5
- N 是奇数。
- 0=A _ 1\lt A _ 2\lt\cdots\lt 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)
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
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- 第一个问题。
示例输入 1
7 0 240 720 1320 1440 1800 2160 3 480 1920 720 1200 0 2160
示例输出 1
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.
示例输入 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