CF1574C Slay the Dragon

最近，Petya 了解到了一款新游戏“Slay the Dragon”。顾名思义，玩家需要与龙战斗。要打败一条龙，你需要杀死它并保卫你的城堡。为此，玩家拥有 $n$ 名英雄，第 $i$ 名英雄的力量为 $a_i$。 根据游戏规则，必须派出一名英雄去杀死龙，其余所有英雄将负责防守城堡。如果龙的防御力为 $x$，则必须派出一名力量至少为 $x$ 的英雄去杀死它。如果龙的攻击力为 $y$，则负责防守城堡的所有英雄的总力量之和必须至少为 $y$。 玩家可以用 1 枚金币将任意一名英雄的力量提升 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$，此时英雄的力量为 $[3, 6, 3, 3]$。可以选择第一名英雄去杀死龙。 要打败第二条龙，可以将第二名和第三名英雄的力量各提升 $1$，此时英雄的力量为 $[3, 7, 3, 3]$。可以选择第二名英雄去杀死龙。 要打败第三条龙，可以将所有英雄的力量都提升 $1$，此时英雄的力量为 $[4, 7, 3, 4]$。可以选择第四名英雄去杀死龙。 要打败第四条龙，无需提升英雄的力量，选择第三名英雄去杀死龙即可。 要打败第五条龙，可以将第二名英雄的力量提升 $2$，此时英雄的力量为 $[3, 8, 2, 3]$。可以选择第二名英雄去杀死龙。 由 ChatGPT 4.1 翻译