CF1119D.Frets On Fire

Miyako came to the flea kingdom with a ukulele. She became good friends with local flea residents and played beautiful music for them every day.

In return, the fleas made a bigger ukulele for her: it has $n$ strings, and each string has $(10^{18} + 1)$ frets numerated from $0$ to $10^{18}$. The fleas use the array $s_1, s_2, \ldots, s_n$ to describe the ukulele's tuning, that is, the pitch of the $j$-th fret on the $i$-th string is the integer $s_i + j$.

Miyako is about to leave the kingdom, but the fleas hope that Miyako will answer some last questions for them.

Each question is in the form of: "How many different pitches are there, if we consider frets between $l$ and $r$ (inclusive) on all strings?"

Miyako is about to visit the cricket kingdom and has no time to answer all the questions. Please help her with this task!

Formally, you are given a matrix with $n$ rows and $(10^{18}+1)$ columns, where the cell in the $i$-th row and $j$-th column ($0 \le j \le 10^{18}$) contains the integer $s_i + j$. You are to answer $q$ queries, in the $k$-th query you have to answer the number of distinct integers in the matrix from the $l_k$-th to the $r_k$-th columns, inclusive.

宫野带着一把尤克里里来到跳蚤王国。她与当地的跳蚤居民成为好朋友，并且每天为他们演奏优美的音乐。

作为回报，跳蚤们为她制作了一把更大的尤克里里：它有 $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$ 列（含端点）的所有元素中不同整数的个数。

The first line contains an integer $n$ ($1 \leq n \leq 100\,000$) — the number of strings.

The second line contains $n$ integers $s_1, s_2, \ldots, s_n$ ($0 \leq s_i \leq 10^{18}$) — the tuning of the ukulele.

The third line contains an integer $q$ ($1 \leq q \leq 100\,000$) — the number of questions.

The $k$-th among the following $q$ lines contains two integers $l_k$，$r_k$ ($0 \leq l_k \leq r_k \leq 10^{18}$) — a question from the fleas.

第一行包含一个整数 $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}$）—— 跳蚤提出的一个问题。

Output one number for each question, separated by spaces — the number of different pitches.

对每个问题输出一个数字，数字之间用空格分隔——即不同音高的数量。

For the first example, the pitches on the $6$ 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$.

对于第一个例子，6根弦在各品上的音高如下：

$$\begin{matrix} \textbf{品} & \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}$$

在第7品上有5个不同的音高：$8, 10, 11, 12, 16$。

在第0、1、2品上共有10个不同的音高：$1, 2, 3, 4, 5, 6, 7, 9, 10, 11$。