Gaining Rating
Contest: Codeforces Round 839 (Div. 3)
Difficulty rating: 2200
Tags: binary search, greedy, implementation, math, sortings, two pointers

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.

Input format:
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$$$.

Output format:
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.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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 the second test case, it can be proven that whichever games Monocarp plays, he can't get his rating higher than $$$4$$$.

Example input:
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

Example output:
20
-1
2

Editorial:
After parsing the statement, you can understand that Monocarp plays cyclically: in one cycle, he chooses some order of opponents and play with them in that order. Then repeats again and again, until he gains desired rating at some moment.
So, firstly, let's prove that (in one cycle) it's optimal to play against opponents in increasing order of their skills. Suppose you play with opponents in some order $$$ord$$$ and there is a position where $$$a[ord_i] > a[ord_{i+1}]$$$, if you swap $$$ord_i$$$ and $$$ord_{i+1}$$$ you won't lose anything and may even gain extra wins. It means that the total gain after playing one cycle in increasing order in greater or equal than playing in any other order.
In other words, we can sort array $$$a$$$ and play against them cyclically in that order. Monocarp's list of games will look like several full cycles and some prefix. The problem is that there can be many cycles, and we need to skip them in a fast way.
How one cycle looks? Monocarp starts with some $$$x$$$ wins first $$$p$$$ games and then loses all other games ($$$m$$$ games where $$$m = n - p$$$). The maximum rating he gains is $$$x + p$$$ and the resulting rating after all games is $$$x + p - m$$$.
We can already find several conditions of leaving a cycle: if $$$x + p \ge y$$$ then Monocarp gets what he wants and stops; otherwise, if $$$x + p - m \le x$$$ (or $$$p - m \le 0$$$) he will never gain the desired rating, since in the next cycle the number of wins $$$p' \le p$$$, since his starting rating $$$x + p - m \le x$$$.
Otherwise, if $$$x + p < y$$$ and $$$p - m > 0$$$, he will start one more cycle with rating $$$x' = x + p - m$$$ and will gain the desired rating $$$y$$$, eventually. So, how to find the number of games $$$p$$$ he will win for a starting rating $$$x$$$?
Let's calculate two values for a given sorted skill array $$$a$$$: for each $$$i$$$ let's calculate $$$t_i$$$ — the minimum starting rating Monocarp need to win opponent $$$i$$$ (and all opponent before) and $$$b_i$$$ — the rating he'll get after winning the $$$i$$$-th opponent.
We can calculate these values in one iteration (we'll use $$$0$$$-indexation): $$$t_0 = a_0$$$, $$$b_0 = a_0 + 1$$$; then for each $$$i > 0$$$ if $$$b_{i - 1} \ge a_i$$$ then $$$t_i = t_{i - 1}$$$ and $$$b_i = b_{i - 1} + 1$$$, otherwise $$$t_i = a_i - i$$$ and $$$b_i = a_i + 1$$$.
Now, knowing values $$$t_i$$$ it's easy to find the number of wins $$$p$$$ for a starting rating $$$x$$$: $$$p$$$ is equal to minimum $$$j$$$ such that $$$t_j > x$$$ (don't forget, $$$0$$$-indexation). Or the first position in array $$$t$$$ with value strictly greater than $$$x$$$. We can search it with standard $$$\text{upper_bound}$$$ function, since array $$$t$$$ is sorted.
Okay, we found the number of wins $$$p$$$ for the current $$$x$$$. Let's just calculate how many cycles $$$k$$$ Monocarp will make with exactly $$$p$$$ wins. There are only two conditions that should be met in order to break this cycle: either Monocarp reaches rating $$$y$$$ — it can be written as inequality $$$x + k (p - m) + p \ge y$$$, or the number of wins increases (starting rating becomes greater or equal than $$$t_p$$$), i.e. $$$x + k (p - m) \ge t_p$$$.
From the first inequality, we get minimum $$$k_1 = \left\lceil \frac{y - x - p}{p - m} \right\rceil$$$ and from the second one — $$$k_2 = \left\lceil \frac{t_p - x}{p - m} \right\rceil$$$. As a result, we can claim that Monocarp will repeat the current cycle exactly $$$k = \min(k_1, k_2)$$$ times and either finish in the next turn or the number of wins will change.
So, we can skip these $$$k$$$ equal cycles: we can increase answer by $$$kn$$$ and current rating by $$$k(p - m)$$$. Since we skip equal cycles, then at each step we either finish (with success or $$$-1$$$), or the number of wins $$$p$$$ increases. Since $$$p$$$ is bounded by $$$n$$$, we will make no more than $$$n$$$ skips, and total complexity is $$$O(n \log n)$$$ because of initial sorting and calls of $$$\text{upper_bound}$$$.