CF1574C.Slay the Dragon

Recently, Petya learned about a new game "Slay the Dragon". As the name suggests, the player will have to fight with dragons. To defeat a dragon, you have to kill it and defend your castle. To do this, the player has a squad of $n$ heroes, the strength of the $i$-th hero is equal to $a_i$.

According to the rules of the game, exactly one hero should go kill the dragon, all the others will defend the castle. If the dragon's defense is equal to $x$, then you have to send a hero with a strength of at least $x$ to kill it. If the dragon's attack power is $y$, then the total strength of the heroes defending the castle should be at least $y$.

The player can increase the strength of any hero by $1$ for one gold coin. This operation can be done any number of times.

There are $m$ dragons in the game, the $i$-th of them has defense equal to $x_i$ and attack power equal to $y_i$. Petya was wondering what is the minimum number of coins he needs to spend to defeat the $i$-th dragon.

Note that the task is solved independently for each dragon (improvements are not saved).

最近，Petya 学习了一款新游戏《屠龙勇士》。顾名思义，玩家需要与巨龙战斗。要击败一条巨龙，你必须杀死它并保卫自己的城堡。为此，玩家拥有一支由 $n$ 名英雄组成的队伍，其中第 $i$ 名英雄的力量值为 $a_i$。

根据游戏规则，恰好一名英雄前去击杀巨龙，其余所有英雄则负责守卫城堡。若巨龙的防御力为 $x$，则必须派遣一名力量值 至少为 $x$ 的英雄去击杀它；若巨龙的攻击力为 $y$，则守卫城堡的所有英雄的总力量值应 至少为 $y$。

玩家可花费 1 枚金币将任意一名英雄的力量值提升 1 点，该操作可执行任意多次。

游戏中共有 $m$ 条巨龙，其中第 $i$ 条巨龙的防御力为 $x_i$、攻击力为 $y_i$。Petya 想知道：击败第 $i$ 条巨龙所需的最少金币数量是多少？

注意：每条巨龙的挑战是独立求解的（即对某条巨龙所做的力量提升不会保留到后续挑战中）。

The first line contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — number of heroes.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^{12}$), where $a_i$ is the strength of the $i$-th hero.

The third line contains a single integer $m$ ($1 \le m \le 2 \cdot 10^5$) — the number of dragons.

The next $m$ lines contain two integers each, $x_i$ and $y_i$ ($1 \le x_i \le 10^{12}; 1 \le y_i \le 10^{18}$) — defense and attack power of the $i$-th dragon.

第一行包含一个整数 $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$ 条巨龙的防御力和攻击力。

Print $m$ lines, $i$-th of which contains a single integer — the minimum number of coins that should be spent to defeat the $i$-th dragon.

输出 $m$ 行，其中第 $i$ 行包含一个整数——击败第 $i$ 条龙所需的最少金币数。

To defeat the first dragon, you can increase the strength of the third hero by $1$, then the strength of the heroes will be equal to $[3, 6, 3, 3]$. To kill the dragon, you can choose the first hero.

To defeat the second dragon, you can increase the forces of the second and third heroes by $1$, then the strength of the heroes will be equal to $[3, 7, 3, 3]$. To kill the dragon, you can choose a second hero.

To defeat the third dragon, you can increase the strength of all the heroes by $1$, then the strength of the heroes will be equal to $[4, 7, 3, 4]$. To kill the dragon, you can choose a fourth hero.

To defeat the fourth dragon, you don't need to improve the heroes and choose a third hero to kill the dragon.

To defeat the fifth dragon, you can increase the strength of the second hero by $2$, then the strength of the heroes will be equal to $[3, 8, 2, 3]$. To kill the dragon, you can choose a second hero.

要击败第一条龙，你可以将第三位英雄的力量提升 $1$，此时各位英雄的力量将变为 $[3, 6, 3, 3]$。为击杀该龙，可选择第一位英雄。

要击败第二条龙，你可以将第二位和第三位英雄的力量各提升 $1$，此时各位英雄的力量将变为 $[3, 7, 3, 3]$。为击杀该龙，可选择第二位英雄。

要击败第三条龙，你可以将所有英雄的力量各提升 $1$，此时各位英雄的力量将变为 $[4, 7, 3, 4]$。为击杀该龙，可选择第四位英雄。

要击败第四条龙，无需提升任何英雄的力量，直接选择第三位英雄即可击杀该龙。

要击败第五条龙，你可以将第二位英雄的力量提升 $2$，此时各位英雄的力量将变为 $[3, 8, 2, 3]$。为击杀该龙，可选择第二位英雄。