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

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

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.


-----Examples-----

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
Output
20
-1
2


-----Note-----

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

Monocarp plays against the $2$-nd opponent to increase rating ($2 \to 3$);

Monocarp plays against the $1$-st opponent to increase rating ($3 \to 4$);

Monocarp plays against the $4$-th opponent to increase rating ($4 \to 5$);

Monocarp plays against the $5$-th opponent to increase rating ($5 \to 6$);

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$);

After that, Monocarp will repeat steps 1-5 again. After $14$ games, he has played twice with each opponent and get final rating $4$.

Monocarp plays against the $1$-st opponent to increase rating ($4 \to 5$);

Monocarp plays against the $2$-nd opponent to increase rating ($5 \to 6$);

Monocarp plays against the $4$-th opponent to increase rating ($6 \to 7$);

Monocarp plays against the $5$-th opponent to increase rating ($7 \to 8$);

Monocarp plays against the $7$-th opponent to increase rating ($8 \to 9$);

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

Source: codeforces | Difficulty: HARD
Tags: Sorting

Amortized analysis

Implementation

Greedy algorithms

Mathematics


Solutions:
import math

def solve(n, x, y, a):
	a.sort()
	for i in range(n):
		a[i] -= i
	res = 0
	for (idx, el) in enumerate(a):
		if x >= el:
			continue
		if y - x <= idx:
			return res + (y - x)
		dx = 2 * idx - n
		if dx <= 0:
			if y - x > idx:
				return -1
			return y - x
		if el >= y - idx:
			iters = math.ceil((y - x - idx) / dx)
			res += iters * n
			x += iters * dx
			break
		else:
			iters = math.ceil((el - x) / dx)
			res += iters * n
			x += iters * dx
	return res + (y - x)

def main():
	ans = []
	for _ in range(int(input())):
		(n, x, y) = map(int, input().split())
		a = list(map(int, input().split()))
		ans.append(solve(n, x, y, a))
	print('\n'.join(map(str, ans)))
main()


def solve():
	(n, x, y) = [int(x) for x in input().split()]
	ranks = [int(x) for x in input().split()]
	ranks.sort()
	score = 0
	result = 0
	while True:
		while score < n and x + score >= ranks[score]:
			score += 1
		if x + score >= y:
			result += y - x
			break
		d = 2 * score - n
		if d <= 0:
			result = -1
			break
		m = y
		if score < n and ranks[score] < y:
			m = ranks[score]
		skip_rounds = (m - score - x) // d
		result += skip_rounds * n
		x += skip_rounds * d
		while x + score < m:
			x += d
			result += n
	print(result)
for _ in range(int(input())):
	solve()


t = int(input())
for tes in range(t):
	(n, x, y) = map(int, input().split())
	a = list(map(int, input().split()))
	a.sort()
	if a[0] > x:
		print(-1)
		continue
	ans = 1
	x += 1
	for i in range(1, n):
		if x == y:
			break
		if i <= n // 2 and a[i] > x:
			x = y
			ans = -1
			break
		if x >= a[i]:
			ans += 1
			x += 1
		else:
			if a[i] >= y:
				add = i - (n - i)
				u = y - x
				r = u // add
				x += add * r
				ans += n * r
				if x == y:
					break
				ans += n - i
				x -= n - i
				break
			add = i - (n - i)
			u = a[i] - x
			r = u // add
			x += add * r
			ans += n * r
			if x == a[i]:
				x += 1
				ans += 1
			else:
				ans += n - i
				x -= n - i
				h = y - x
				if h <= i:
					break
				x += i
				ans += i
				x += 1
				ans += 1
	ans += y - x
	print(ans)


from collections import deque
for tea in range(int(input())):
	(n, x, y) = map(int, input().split())
	a = [int(xx) for xx in input().split()]
	a.sort()
	bx = x
	turns = 0
	canBeat = 0
	cantBeat = deque()
	bad = False
	for i in a:
		if x == y:
			break
		turns += 1
		if x >= i:
			x += 1
			canBeat += 1
		else:
			x -= 1
			cantBeat.append(i)
	if x <= bx:
		print(-1)
	elif x >= y:
		print(turns)
	else:
		turns = 0
		x = bx
		if canBeat != n:
			nextToBeat = cantBeat.popleft()
		else:
			nextToBeat = -1
		while x < y:
			if nextToBeat != -1:
				lol = max(min(y - x, nextToBeat - x - canBeat) // (canBeat * 2 - n) - 3, 0)
			else:
				turns += y - x
				break
			x += lol * (canBeat * 2 - n)
			turns += lol * n
			if x + canBeat >= y:
				turns += y - x
				break
			x += canBeat
			turns += canBeat
			while x >= nextToBeat:
				if nextToBeat == -1:
					break
				x += 1
				canBeat += 1
				if canBeat != n:
					nextToBeat = cantBeat.popleft()
				else:
					nextToBeat = -1
				turns += 1
				if x >= y:
					break
			if x >= y:
				break
			x -= n - canBeat
			turns += n - canBeat
		print(turns)


def div_(xx, yy):
	if xx % yy == 0:
		return xx // yy
	else:
		return xx // yy + 1

def search(m):
	mi = 0
	ma = n - 1
	if b[0] > m:
		return 0
	if b[n - 1] <= m:
		return n
	while True:
		if b[(mi + ma) // 2] <= m:
			mi = (mi + ma) // 2
		else:
			ma = (mi + ma) // 2
		if ma - mi <= 1:
			return ma
t = int(input())
for u in range(0, t):
	(n, x, y) = map(int, input().split())
	a = list(map(int, input().split()))
	w = a.sort()
	b = [0] * n
	b[0] = a[0]
	for i in range(1, n):
		b[i] = max(b[i - 1], a[i] - i)
	out = 0
	while True:
		r = search(x)
		if x + r >= y:
			out = out + y - x
			break
		get_1 = r - (n - r)
		if get_1 <= 0:
			out = -1
			break
		if r == n:
			round_ = div_(y - x - r, get_1)
			y = y - x - round_ * get_1
			out = out + round_ * n + y
			break
		else:
			round_ = div_(b[r] - x, get_1)
			if x + get_1 * (round_ - 1) < y - r:
				x = x + get_1 * round_
				out = out + round_ * n
			else:
				round_ = div_(y - x - r, get_1)
				y = y - x - round_ * get_1
				out += round_ * n + y
				break
	print(out)