A15617 · 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 > 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.

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 < 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$ .

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.

输入 #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