C. Slay the Dragon
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Недавно Петя узнал о новой игре «Slay the Dragon». Как видно из названия, игроку предстоит сражаться с драконами, чтобы победить дракона, необходимо его убить и защитить свой замок. Для этого в распоряжении игрока есть отряд из $$$n$$$ героев, сила $$$i$$$-го героя равна $$$a_i$$$.

По правилам игры убивать дракона должен отправиться ровно один герой, все остальные будут защищать замок. Если защита дракона равна $$$x$$$, то на его убийство можно отправлять героя с силой не менее $$$x$$$. Если сила атаки дракона равна $$$y$$$, то суммарная сила героев, защищающих замок, должна быть хотя бы $$$y$$$.

За одну золотую монету игрок может увеличить силу любого из героев на $$$1$$$. Эту операцию можно выполнять любое количество раз.

Всего в игре существует $$$m$$$ драконов, у $$$i$$$-го из них защита $$$x_i$$$, а сила атаки $$$y_i$$$. Пете стало интересно, какое минимальное количество монет ему необходимо потратить, чтобы победить $$$i$$$-го дракона.

Обратите внимание, что задача решается независимо для каждого дракона (улучшения не сохраняются).

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

Первая строка содержит одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — количество героев.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{12}$$$), где $$$a_i$$$ — сила $$$i$$$-го героя.

Третья строка содержит одно целое число $$$m$$$ ($$$1 \le m \le 2 \cdot 10^5$$$) — количество драконов.

Последующие $$$m$$$ строк содержат по два целых числа $$$x_i$$$ и $$$y_i$$$ ($$$1 \le x_i \le 10^{12}; 1 \le y_i \le 10^{18}$$$) — защита и сила атаки $$$i$$$-го дракона.

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

Выведите $$$m$$$ строк, $$$i$$$-я из которых содержит одно целое число — минимальное количество монет, которое необходимо потратить, чтобы победить $$$i$$$-го дракона.

Пример
Входные данные
4
3 6 2 3
5
3 12
7 9
4 14
1 10
8 7
Выходные данные
1
2
4
0
2
Примечание

Для победы над первым драконом можно увеличить силу третьего героя на $$$1$$$, тогда силы героев будут равны $$$[3, 6, 3, 3]$$$. Для убийства дракона можно выбрать первого героя.

Для победы над вторым драконом можно увеличить силы второго и третьего героев на $$$1$$$, тогда силы героев будут равны $$$[3, 7, 3, 3]$$$. Для убийства дракона можно выбрать второго героя.

Для победы над третьим драконом можно увеличить силы всех героев на $$$1$$$, тогда силы героев будут равны $$$[4, 7, 3, 4]$$$. Для убийства дракона можно выбрать четвертого героя.

Для победы над четверым драконом можно не улучшать героев и выбрать третьего героя для убийства дракона.

Для победы над пятым драконом можно увеличить силу второго героя на $$$2$$$, тогда силы героев будут равны $$$[3, 8, 2, 3]$$$. Для убийства дракона можно выбрать второго героя.