CF1119D Frets On Fire

## 题目背景 Miyako 带着尤克里里琴来到跳蚤王国。她与当地的跳蚤居民成为了好朋友，每天为他们演奏美妙的音乐。 作为回报，跳蚤为她做了一个更大的尤克里里琴：它有 $n$ 个弦，每个弦都有从 $0$ 到 $10^{18}$ 的 $10^{18}+1$ 个琴格（用来给琴划分音阶高低）。跳蚤使用数组 $s_1, s_2,......,s_n$ 来描述尤克里里琴的品，也就是说，第 $i$ 个弦上第 $j$ 个琴格的音调是整数 $s_i+j$。 Miyako 即将离开王国，但跳蚤希望 Miyako 能为它们回答最后一些问题。 第 $k$ 个问题是：“在所有弦上，琴格 $l_k$ 与琴格 $r_k$（包括 $l_k$，$r_k$）之间有多少个不同的音调？” Miyako 即将访问蟋蟀王国，没有时间回答所有问题。请你帮助她完成这项任务！ 在形式上，给出一个 $n$ 行 $10^{18}+1$ 列的矩阵，其中第 $i$ 行（$1 \leqslant i \leqslant n$）第 $j$ 列（$0 \leqslant j \leqslant 10^{18}$）中的单元格为整数 $s_i+j$。有 $q$ 个询问，对于第 $k$ 个询问，你需要回答矩阵中从第 $l_k$ 列到第 $r_k$ 列（包括 $l_k$，$r_k$）的不同整数的数量。

第一行包含整数 $n$（$1 \leqslant n \leqslant 10^{5}$），表示弦的数量。 第二行包含 $n$ 个整数 $s_1,s_2,......s_n$ （$0 \leqslant s_i \leqslant 10^{18}$），表示尤克里里琴的品。 第三行包含 $1$ 个整数 $q$（$1 \leqslant q \leqslant 10^5$），表示问题的数量。 以下 $q$ 行中的第 $k$ 个包含两个整数 $l_k, r_k$ （$0 \leqslant l_k \leqslant r_k \leqslant 10^{18}$），表示跳蚤的询问

对于第 $k$ 个询问，输出一个整数，表示 $l_k$ 与 $r_k$ 之间不同音调的数量，每两个整数之间用空格分隔。

For the first example, the pitches on the $66$ strings are as follows. $$\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{matrix}$$ There are $5$ different pitches on fret $7$ — $8, 10, 11, 12, 16$ There are $10$ different pitches on frets $0, 1, 2$ — $1, 2, 3, 4, 5, 6, 7, 9, 10, 11$