D. Frets On Fire
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Мияко приехала в гости в страну блох с укулеле. Она подружилась с блохами и исполняла им прекрасную музыку каждый день.

В благодарность за это блохи изготовили для нее большое укулеле: всего не нем $$$n$$$ струн, на каждой струне $$$(10^{18} + 1)$$$ лад, лады пронумерованы от $$$0$$$ до $$$10^{18}$$$. Блохи описывают это укулеле массивом $$$s_1, s_2, \ldots, s_n$$$, что означает, что $$$j$$$-й лад на $$$i$$$-й струне издает ноту $$$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$$$) — количество вопросов.

В $$$k$$$-й из следующих $$$q$$$ строк находятся два целых числа $$$l_k$$$，$$$r_k$$$ ($$$0 \leq l_k \leq r_k \leq 10^{18}$$$) — очередной вопрос блох.

Выходные данные

Выведите одно целое число для каждого вопросы: число различных нот.

Примеры
Входные данные
6
3 1 4 1 5 9
3
7 7
0 2
8 17
Выходные данные
5 10 18
Входные данные
2
1 500000000000000000
2
1000000000000000000 1000000000000000000
0 1000000000000000000
Выходные данные
2 1500000000000000000
Примечание

В первом примере ноты на $$$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$$$.