最近,Petya了解到了一款新游戏《屠龙》。顾名思义,玩家将不得不与龙战斗。要打败龙,你必须杀死它并保卫你的城堡。为此,玩家拥有一支由 $$$n$$$ 英雄组成的小队,第 $$$i$$$ 个英雄的实力等于 $$$a_i$$$。
根据游戏规则,只有一名英雄去杀龙,其他英雄负责保卫城堡。如果龙的防御等于$$$x$$$,那么你必须派出力量至少为$$$x$$$的英雄来杀死它。如果龙的攻击力是$$$y$$$,那么守城英雄的总实力至少应该是$$$y$$$。
玩家可以用一枚金币将任意英雄的力量提升$$$1$$$。该操作可以进行任意多次。
游戏中有$$$m$$$条龙,其中第$$$i$$$条的防御力等于$$$x_i$$$,攻击力等于$$$y_i$$$。 Petya 想知道他需要花费多少硬币才能击败第 $$$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$$$ 条龙所需花费的最小硬币数。
示例
输入 #1
4 3 6 2 3 5 3 12 7 9 4 14 1 10 8 7
输出 #1
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]$$$。要杀死龙,你可以选择第二个英雄。