CF1772G.Gaining Rating

Monocarp is playing chess on one popular website. He has $n$ opponents he can play with. The $i$-th opponent has rating equal to $a_i$. Monocarp's initial rating is $x$. Monocarp wants to raise his rating to the value $y$ ($y \gt x$).

When Monocarp is playing against one of the opponents, he will win if his current rating is bigger or equal to the opponent's rating. If Monocarp wins, his rating is increased by $1$, otherwise it is decreased by $1$. The rating of his opponent does not change.

Monocarp wants to gain rating $y$ playing as few games as possible. But he can't just grind it, playing against weak opponents. The website has a rule that you should play against all opponents as evenly as possible. Speaking formally, if Monocarp wants to play against an opponent $i$, there should be no other opponent $j$ such that Monocarp has played more games against $i$ than against $j$.

Calculate the minimum possible number of games Monocarp needs to gain rating $y$ or say it's impossible. Note that ratings of Monocarp's opponents don't change, while Monocarp's rating does change.

Monocarp 正在某知名网站上玩国际象棋。他有 $n$ 个可对战的对手，其中第 $i$ 个对手的等级分为 $a_i$。Monocarp 的初始等级分为 $x$，他希望将自己的等级分提升至 $y$（其中 $y > x$）。

当 Monocarp 与某位对手对战时，若他当前的等级分大于或等于该对手的等级分，则他获胜；否则失败。若 Monocarp 获胜，他的等级分增加 $1$；若失败，则等级分减少 $1$。对手的等级分始终保持不变。

Monocarp 希望以最少的对局数达到等级分 $y$。但他不能只反复挑战弱对手“刷分”。该网站有一条规则：玩家必须尽可能均匀地与所有对手对战。形式化地说，若 Monocarp 想要与对手 $i$ 进行一局对战，则不能存在另一对手 $j$，使得 Monocarp 已与 $i$ 对战的局数多于已与 $j$ 对战的局数。

请计算 Monocarp 达到等级分 $y$ 所需的最少对局数；若不可能达成，请说明其不可能性。注意：Monocarp 各对手的等级分恒定不变，而 Monocarp 自身的等级分会随对局结果动态变化。

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.

The first line of each test case contains three integers $n$, $x$ and $y$ ($1 \le n \le 2 \cdot 10^5$; $1 \le x \lt y \le 10^{12}$) — the number of Monocarp's opponents, his initial and desired ratings.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^{12}$) — ratings of Monocarp's opponents.

Additional constraint on the input: the total sum of $n$ over all $t$ test cases doesn't exceed $2 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 10^4$）—— 测试用例的数量。

每个测试用例的第一行包含三个整数 $n$、$x$ 和 $y$（$1 \le n \le 2 \cdot 10^5$；$1 \le x \lt y \le 10^{12}$）—— 分别表示 Monocarp 的对手数量、他的初始评分和目标评分。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^{12}$）—— 表示 Monocarp 各对手的评分。

输入的额外约束：所有 $t$ 个测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

For each test case, print a single integer — the minimum number of games Monocarp needs to play to gain rating $y$, or $-1$ if it's impossible.

对于每个测试用例，输出一个整数——Monocarp 为获得评分 $y$ 所需进行的最少比赛场数；若不可能实现，则输出 $-1$。

In the first test case, Monocarp can use the following strategy:

1. Monocarp plays against the $2$-nd opponent to increase rating ($2 \to 3$);
2. Monocarp plays against the $1$-st opponent to increase rating ($3 \to 4$);
3. Monocarp plays against the $4$-th opponent to increase rating ($4 \to 5$);
4. Monocarp plays against the $5$-th opponent to increase rating ($5 \to 6$);
5. Now Monocarp have to play with remaining three opponents. So, he will lose $3$ times and get rating $3$ ($6 \to 5 \to 4 \to 3$);
6. After that, Monocarp will repeat steps 1-5 again. After $14$ games, he has played twice with each opponent and get final rating $4$.
7. Monocarp plays against the $1$-st opponent to increase rating ($4 \to 5$);
8. Monocarp plays against the $2$-nd opponent to increase rating ($5 \to 6$);
9. Monocarp plays against the $4$-th opponent to increase rating ($6 \to 7$);
10. Monocarp plays against the $5$-th opponent to increase rating ($7 \to 8$);
11. Monocarp plays against the $7$-th opponent to increase rating ($8 \to 9$);
12. Monocarp plays against the $3$-rd opponent to increase rating ($9 \to 10$);

In total, Monocarp, played twice against the $6$-th opponent and three times against other opponents and got rating $10$ in $14 + 6 = 20$ games.

In the second test case, it can be proven that whichever games Monocarp plays, he can't get his rating higher than $4$.

在第一个测试用例中，Monocarp 可采用如下策略：

1. Monocarp 与第 $2$ 位对手对战以提升评分（$2 \to 3$）；
2. Monocarp 与第 $1$ 位对手对战以提升评分（$3 \to 4$）；
3. Monocarp 与第 $4$ 位对手对战以提升评分（$4 \to 5$）；
4. Monocarp 与第 $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. Monocarp 与第 $2$ 位对手对战以提升评分（$5 \to 6$）；
9. Monocarp 与第 $4$ 位对手对战以提升评分（$6 \to 7$）；
10. Monocarp 与第 $5$ 位对手对战以提升评分（$7 \to 8$）；
11. Monocarp 与第 $7$ 位对手对战以提升评分（$8 \to 9$）；
12. Monocarp 与第 $3$ 位对手对战以提升评分（$9 \to 10$）。

总计，Monocarp 与第 $6$ 位对手交手两次，与其他每位对手各交手三次，在 $14 + 6 = 20$ 场比赛中获得最终评分 $10$。

在第二个测试用例中，可以证明：无论 Monocarp 如何安排对战顺序，其评分均无法超过 $4$。