CF1772G Gaining Rating

Monocarp 正在一个流行的网站上下棋。他有 $n$ 个可以对战的对手，第 $i$ 个对手的分数为 $a_i$。Monocarp 的初始分数为 $x$。Monocarp 想要将自己的分数提升到 $y$（$y > x$）。 当 Monocarp 与某个对手对弈时，如果他的当前分数大于等于对手的分数，则他获胜，分数增加 $1$，否则分数减少 $1$。对手的分数不会变化。 Monocarp 想用尽可能少的对局数将分数提升到 $y$。但他不能只和弱对手刷分。网站有一条规则：你必须尽量平均地与所有对手对弈。正式地说，如果 Monocarp 想和第 $i$ 个对手对弈，则不存在另一个对手 $j$，使得他与 $i$ 对弈的次数比与 $j$ 多。 计算 Monocarp 至少需要进行多少局才能将分数提升到 $y$，或者输出 $-1$ 表示不可能。注意，对手的分数不会变化，而 Monocarp 的分数会变化。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例的第一行包含三个整数 $n$、$x$ 和 $y$（$1 \le n \le 2 \times 10^5$；$1 \le x < y \le 10^{12}$），分别表示 Monocarp 的对手数量、初始分数和目标分数。 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^{12}$），表示每个对手的分数。 输入的额外限制：所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。

对于每个测试用例，输出一个整数，表示 Monocarp 至少需要进行的对局数，或者如果不可能达到目标分数则输出 $-1$。

在第一个测试用例中，Monocarp 可以采用如下策略： 1. Monocarp 先与第 $2$ 个对手对弈提升分数（$2 \to 3$）； 2. 再与第 $1$ 个对手对弈提升分数（$3 \to 4$）； 3. 再与第 $4$ 个对手对弈提升分数（$4 \to 5$）； 4. 再与第 $5$ 个对手对弈提升分数（$5 \to 6$）； 5. 现在 Monocarp 必须与剩下的三个对手对弈，因此会输 $3$ 次，分数变为 $3$（$6 \to 5 \to 4 \to 3$）； 6. 之后，Monocarp 会重复步骤 1-5。经过 $14$ 局后，他与每个对手都对弈了两次，分数变为 $4$。 7. Monocarp 与第 $1$ 个对手对弈提升分数（$4 \to 5$）； 8. 与第 $2$ 个对手对弈提升分数（$5 \to 6$）； 9. 与第 $4$ 个对手对弈提升分数（$6 \to 7$）； 10. 与第 $5$ 个对手对弈提升分数（$7 \to 8$）； 11. 与第 $7$ 个对手对弈提升分数（$8 \to 9$）； 12. 与第 $3$ 个对手对弈提升分数（$9 \to 10$）； 总共，Monocarp 与第 $6$ 个对手对弈了两次，与其他对手对弈了三次，共进行了 $14 + 6 = 20$ 局，最终分数达到 $10$。 在第二个测试用例中，可以证明无论如何对弈，Monocarp 的分数都无法超过 $4$。 由 ChatGPT 4.1 翻译