← 返回题目列表

Codeforces · 1119/D

D. 烦恼着火

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

宫子带着尤克里里来到了跳蚤王国。她和当地的跳蚤居民成了好朋友,每天为他们演奏优美的音乐。

作为回报,跳蚤为她制作了一把更大的尤克里里:它有 $$$n$$$ 琴弦,每个琴弦都有 $$$(10^{18} + 1)$$$ 音品,编号从 $$$0$$$ 到 $$$10^{18}$$$。跳蚤使用数组 $$$s_1, s_2, \ldots, s_n$$$ 来描述尤克里里的调音,即第 $$$i$$$ 弦上第 $$$j$$$ 音品的音高为整数 $$$s_i + j$$$。

宫子即将离开王国,但跳蚤们希望宫子能为他们回答最后一些问题。

每个问题的形式如下:“如果我们考虑所有琴弦上 $$$l$$$ 和 $$$r$$$(包括)之间的品格,有多少种不同的音高?”

宫子即将访问板球王国,没有时间回答所有问题。请帮助她完成这项任务!

正式地,您将获得一个包含 $$$n$$$ 行和 $$$(10^{18}+1)$$$ 列的矩阵,其中 $$$i$$$ 行和 $$$j$$$ 列 ($$$0 \le j \le 10^{18}$$$) 中的单元格包含整数 $$$s_i + j$$$。您要回答 $$$q$$$ 查询,在第 $$$k$$$ 查询中,您必须回答矩阵中从第 $$$l_k$$$ 列到第 $$$r_k$$$ 列(含)的不同整数的数量。

输入

第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 100\,000$$$) — 字符串的数量。

第二行包含 $$$n$$$ 整数 $$$s_1, s_2, \ldots, s_n$$$ ($$$0 \leq s_i \leq 10^{18}$$$) — 尤克里里琴的调音。

第三行包含一个整数 $$$q$$$ ($$$1 \leq q \leq 100\,000$$$) — 问题数。

以下 $$$q$$$ 行中的第 $$$k$$$ 行包含两个整数 $$$l_k$$$,$$$r_k$$$ ($$$0 \leq l_k \leq r_k \leq 10^{18}$$$) – 跳蚤的一个问题。

输出

为每个问题输出一个数字,用空格分隔——不同音调的数量。

示例

输入 #1

6
3 1 4 1 5 9
3
7 7
0 2
8 17

输出 #1

5 10 18

输入 #2

2
1 500000000000000000
2
1000000000000000000 1000000000000000000
0 1000000000000000000

输出 #2

2 1500000000000000000

注意

对于第一个示例,$$$6$$$ 弦上的音高如下。

$$$$$$ \begin{matrix} \textbf{Fret} & \textbf{0} & \textbf{1} & \textbf{2} & \textbf{3} & \textbf{4} & \textbf{5} & \textbf{6} & \textbf{7} & \ldots \\ s_1: & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & \dots \\ s_2: & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & \dots \\ s_3: & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & \dots \\ s_4: & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & \dots \\ s_5: & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & \dots \\ s_6: & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & \dots \end{矩阵} $$$$$$

品格上有 $$$5$$$ 不同的音高 $$$7$$$ — $$$8, 10, 11, 12, 16$$$。

音品上有 $$$10$$$ 不同的音高 $$$0, 1, 2$$$ — $$$1, 2, 3, 4, 5, 6, 7, 9, 10, 11$$$。