AT_abc305_d.[ABC305D] Sleep Log

高桥君正在记录自己的睡眠情况。睡眠记录用一个奇数长度的数列 $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$ 个询问给出一组整数 $(l_i, r_i)$，满足 $0\leq l_i\leq r_i\leq A_N$。

• 从开始记录后的第 $l_i$ 分钟到第 $r_i$ 分钟这 $r_i-l_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$ 个询问的答案，结果为整数。

限制条件

• $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)$
• 输入均为整数

样例解释 1

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

每个询问的答案如下：

• 从记录开始后第 $480$ 分钟到第 $1920$ 分钟，高桥君在 $480$ 分钟到 $720$ 分钟、$1320$ 分钟到 $1440$ 分钟、$1800$ 分钟到 $1920$ 分钟这三段时间睡觉。总睡眠时间为 $240+120+120=480$ 分钟。
• 从 $720$ 分钟到 $1200$ 分钟期间，高桥君没有睡觉。总睡眠时间为 $0$ 分钟。
• 从 $0$ 分钟到 $2160$ 分钟期间，高桥君在 $240$ 分钟到 $720$ 分钟、$1320$ 分钟到 $1440$ 分钟、$1800$ 分钟到 $2160$ 分钟这三段时间睡觉。总睡眠时间为 $480+120+360=960$ 分钟。

因此，分别输出 $480, 0, 960$。

由 ChatGPT 4.1 翻译