G. Поднятие рейтинга
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Монокарп играет в шахматы на одном популярном сайте. На этом сайте у него есть $$$n$$$ соперников. Рейтинг $$$i$$$-го соперника равен $$$a_i$$$. Изначальный рейтинг Монокарпа равен $$$x$$$. Монокарп хочет достичь рейтинга $$$y$$$ ($$$y > x$$$).

Когда Монокарп играет партию, он побеждает, если его текущий рейтинг больше или равен рейтинга противника. В случае победы рейтинг Монокарпа повышается на $$$1$$$, в случае поражения — понижается на $$$1$$$. Рейтинг его противника не меняется.

Монокарп хочет за минимальное кол-во партий достигнуть рейтинга $$$y$$$. Но сайт не позволяет ему легко набирать рейтинг в играх против слабых игроков, требуя, чтобы Монокарп играл со всеми противниками примерно равное количество партий. Формально, Монокарп может сыграть партию с противником $$$i$$$ только если нет другого противника $$$j$$$ такого, что Монокарп сыграл против $$$i$$$ больше раз, чем против $$$j$$$.

Посчитайте минимальное кол-во партий, которое нужно сыграть Монокарпу, чтобы достичь рейтинга $$$y$$$, или скажите, что это невозможно. Заметьте, что рейтинги противников Монокарпа остаются неизменными, в отличие от рейтинга самого Монокарпа.

Входные данные

В первой строке задано одно целое число $$$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}$$$) — количество противников Монокарпа, его первоначальный и желаемый рейтинги.

Во второй строке каждого набора заданы $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^{12}$$$) — рейтинги противников Монокарпа.

Гарантируется, что сумма $$$n$$$ по всем $$$t$$$ наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно число — минимальное количество партий, которые нужно сыграть Монокарпу, чтобы получить рейтинг $$$y$$$, или $$$-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
Выходные данные
20
-1
2
Примечание

В первом наборе входных данных, Монокарп может использовать следующую стратегию:

  1. Монокарп играет против $$$2$$$-го соперника и увеличивает рейтинг ($$$2 \to 3$$$);
  2. Монокарп играет против $$$1$$$-го соперника и увеличивает рейтинг ($$$3 \to 4$$$);
  3. Монокарп играет против $$$4$$$-го соперника и увеличивает рейтинг ($$$4 \to 5$$$);
  4. Монокарп играет против $$$5$$$-го соперника и увеличивает рейтинг ($$$5 \to 6$$$);
  5. Теперь Монокарп должен сыграть с оставшимися тремя соперниками. Он проиграет $$$3$$$ раза и получит рейтинг $$$3$$$ ($$$6 \to 5 \to 4 \to 3$$$);
  6. После этого Монокарп повторит шаги 1-5 два раза. После $$$14$$$ партий получится, что он сыграл дважды к каждым противников и его финальный рейтинг равен $$$4$$$.
  7. Монокарп играет против $$$1$$$-го соперника и увеличивает рейтинг ($$$4 \to 5$$$);
  8. Монокарп играет против $$$2$$$-го соперника и увеличивает рейтинг ($$$5 \to 6$$$);
  9. Монокарп играет против $$$4$$$-го соперника и увеличивает рейтинг ($$$6 \to 7$$$);
  10. Монокарп играет против $$$5$$$-го соперника и увеличивает рейтинг ($$$7 \to 8$$$);
  11. Монокарп играет против $$$7$$$-го соперника и увеличивает рейтинг ($$$8 \to 9$$$);
  12. Монокарп играет против $$$3$$$-го соперника и увеличивает рейтинг ($$$9 \to 10$$$);
В результате Монокарп сыграл дважды с $$$6$$$-м противником и трижды со всеми остальными, получив рейтинг $$$10$$$ за $$$14 + 6 = 20$$$ партий.

Во втором наборе можно показать, что какие бы партии не сыграл Монокарп, он не сможет получить рейтинг выше $$$4$$$.