D. Фестиваль деревянных игрушек
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В одном небольшом городке есть мастерская, специализирующаяся на работах по дереву. Так как город маленький, в ней работают всего три резчика.

Скоро в городе планируется фестиваль деревянных игрушек. Работники мастерской хотят к нему подготовиться.

Они знают, что $$$n$$$ человек придёт в мастерскую с просьбой сделать деревянную игрушку. Люди разные и могут хотеть разные игрушки. Для простоты обозначим паттерн игрушки, которую хочет $$$i$$$-й человек за $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$).

Каждый из резчиков может заранее выбрать какой-то паттерн $$$x$$$ ($$$1 \le x \le 10^9$$$), разные резчики могут выбрать разные паттерны. $$$x$$$ - натуральное число. За время подготовки к фестивалю резчики идеально отработают технику выполнения игрушки выбранного паттерна, что позволит им мгновенно вырезать её из дерева. Чтобы сделать игрушку паттерна $$$y$$$ резчику, выбравшему паттерн $$$x$$$, понадобится $$$|x - y|$$$ времени, ведь чем больше игрушка похожа на ту, что он умеет делать мгновенно, тем быстрее резчик справится с работой.

В день фестиваля, когда очередной человек зайдёт в мастерскую с просьбой сделать деревянную игрушку, резчики могут выбрать, кто из них примется за работу. При этом резчики очень умелые люди и могут одновременно выполнять заказы для разных людей.

Так как люди не любят ждать, резчики хотят выбрать паттерны для подготовки таким образом, чтобы максимальное время ожидания среди всех людей было как можно меньше.

Выведите наилучшее максимальное время ожидания, которого смогут добиться резчики.

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

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

Далее следуют описания наборов.

В первой строке набора содержится единственное целое число $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — количество людей, которые придут в мастерскую.

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

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

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

Выведите $$$t$$$ чисел, каждое из которых является ответом на соответствующий набор — наилучшее максимальное время ожидания, которого смогут добиться резчики.

Пример
Входные данные
5
6
1 7 7 9 9 9
6
5 4 2 1 30 60
9
14 19 37 59 1 4 4 98 73
1
2
6
3 10 1 17 15 11
Выходные данные
0
2
13
0
1
Примечание

В первом примере входных данных резчики могут выбрать паттерны $$$1$$$, $$$7$$$, $$$9$$$ для подготовки.

Во втором примере входных данных резчики могут выбрать паттерны $$$3$$$, $$$30$$$, $$$60$$$ для подготовки.

Во третьем примере входных данных резчики могут выбрать паттерны $$$14$$$, $$$50$$$, $$$85$$$ для подготовки.