← 返回题目列表

AtCoder · abc305_d

G. 睡眠日志

中文机器翻译题面 查看原题

分数: 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