Monocarp 正在一个热门网站上下棋。他有 $$$n$$$ 可以一起玩的对手。第 $$$i$$$ 个对手的评级等于 $$$a_i$$$。 Monocarp 的初始评级为 $$$x$$$。 Monocarp 希望将其评级提高到值 $$$y$$$ ($$$y > x$$$)。
当Monocarp与其中一位对手对战时,如果他当前的等级大于或等于对手的等级,他就会获胜。如果 Monocarp 获胜,他的评级会增加 $$$1$$$,否则会减少 $$$1$$$。对手的评分没有改变。
Monocarp 希望通过玩尽可能少的游戏获得 $$$y$$$ 评级。但他不能只是磨磨蹭蹭,与弱小的对手比赛。该网站有一条规则,即您应该尽可能均匀地与所有对手进行比赛。正式来说,如果 Monocarp 想要与对手 $$$i$$$ 比赛,则不应有其他对手 $$$j$$$,这样 Monocarp 与 $$$i$$$ 的比赛次数多于与 $$$j$$$ 的比赛次数。
计算 Monocarp 需要获得评级 $$$y$$$ 的最小可能游戏数量,或者说这是不可能的。请注意,Monocarp 的对手的评分不会改变,而 Monocarp 的评分会改变。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例的第一行包含三个整数 $$$n$$$、$$$x$$$ 和 $$$y$$$ ($$$1 \le n \le 2 \cdot 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}$$$) — Monocarp 对手的评分。
输入的附加约束:所有 $$$t$$$ 测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,打印一个整数 - Monocarp 需要玩的最小游戏数才能获得评级 $$$y$$$,如果不可能,则打印 $$$-1$$$。
示例
输入 #1
3 7 2 10 3 1 9 2 5 20 8 7 1 10 3 1 9 2 5 20 8 5 10 12 100 1 200 11 300
输出 #1
20 -1 2
注意
在第一个测试用例中,Monocarp 可以使用以下策略:
1. Monocarp 与 $$$2$$$-nd 对手对战以提高等级($$$2 \to 3$$$);
2. Monocarp 与 $$$1$$$-st 对手对战以提高等级($$$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$$$-st 对手对战以提高等级($$$4 \to 5$$$);
8. Monocarp 与 $$$2$$$-nd 对手对战以提高等级($$$5 \to 6$$$);
9. Monocarp 与第 $$$4$$$ 个对手对战以提高等级($$$6 \to 7$$$);
10. Monocarp 与第 $$$5$$$ 个对手对战以提高等级($$$7 \ 至 8$$$);
11. Monocarp 与第 $$$7$$$ 对手对战以提高等级($$$8 \to 9$$$);
12. Monocarp 与 $$$3$$$-rd 对手对战以提高等级($$$9 \to 10$$$);
在第二个测试用例中,可以证明无论 Monocarp 玩什么游戏,他的评分都不能高于 $$$4$$$。