D. Игра с миллиардом игроков
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
NemesisTheory - Rose At Nightfall
⠀

Вы следите за чемпионатом мира по «Игре с миллиардом игроков». Участвует $$$10^9$$$ игроков, и вы хотите предсказать $$$p$$$ — финальный рейтинг Годфлекса, вашего любимого стримера. После анализа недавних матчей вы уверены, что $$$l \leq p \leq r$$$, но ничего больше не знаете.

Существует $$$n$$$ предложений от букмекерской конторы в игре. В $$$i$$$-м предложении букмекер предлагает оценку $$$a_i$$$ финального рейтинга Годфлекса. Для каждого предложения вы должны выбрать ровно одно из следующих действий:

  • Проигнорировать предложение.
  • Принять предложение, заявив, что $$$p \leq a_i$$$. Если вы правы, вы зарабатываете $$$|p-a_i|$$$ робокоина; в противном случае вы теряете $$$|p-a_i|$$$ робокоина.
  • Принять предложение, заявив, что $$$p \geq a_i$$$. Если вы правы, вы зарабатываете $$$|p-a_i|$$$ робокоина; в противном случае вы теряете $$$|p-a_i|$$$ робокоина.

После того как вы решите, как поступить со всеми предложениями, игра Миллиард Игроков будет сыграна. Годфлекс занимает позицию $$$p$$$ в $$$[l, r]$$$, и затем все принятые предложения будут применены.

Ваш общий счет — это количество робокоинов, которое вы гарантированно заработаете, то есть минимальное количество робокоинов, которое вы заработаете при всех возможных значениях $$$p$$$ в $$$[l, r]$$$. Найдите максимальный возможный счет, который вы можете гарантировать.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$l$$$, $$$r$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq l \leq r \leq 10^9$$$) — количество предложений и возможный диапазон финального рейтинга Годфлекса.

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — оценки букмекера рейтинга Годфлекса в каждом предложении.

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

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

Для каждого набора входных данных выведите одну строку, содержащую целое число: максимальный возможный счет, который вы можете гарантировать.

Пример
Входные данные
4
1 1 5
3
2 100 100
50 200
5 1 10
5 7 3 9 1
5 6 10
9 3 1 7 5
Выходные данные
0
150
12
13
Примечание

В первом наборе входных данных есть только одно предложение.

  • Если вы игнорируете предложение, ваш счет равен $$$0$$$;
  • если вы принимаете предложение, заявляя, что $$$p \leq 3$$$, ваш счет равен $$$-2$$$ (достигается при $$$p = 5$$$, что заставляет вас потерять $$$|5-3| = 2$$$ робокоина);
  • если вы принимаете предложение, заявляя, что $$$p \geq 3$$$, ваш счет равен $$$-2$$$ (достигается при $$$p = 1$$$, что заставляет вас потерять $$$|1-3| = 2$$$ робокоина).

Таким образом, максимальный возможный счет равен $$$0$$$.

Во втором наборе входных данных оптимально принять предложения, заявляя, что $$$p \geq 50$$$ и $$$p \leq 200$$$. Поскольку $$$p$$$ должен быть $$$100$$$, вы зарабатываете $$$|100-50| + |100-200| = 150$$$ робокоинов.