C. Кубики и мешки
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Есть $$$n$$$ кубиков, пронумерованных от $$$1$$$ до $$$n$$$. Кубик $$$i$$$ имеет вес $$$a_i$$$.

У Пака Чанека есть $$$3$$$ мешка с номерами от $$$1$$$ до $$$3$$$, которые изначально пусты. Каждый кубик Пак Чанек должен положить в один из мешков. После этого в каждом мешке должен оказаться хотя бы один кубик.

После того, как Пак Чанек разложит кубики, Бу Денгклек возьмет ровно по одному кубику из каждого мешка. Пусть $$$w_j$$$ — вес кубика, который Бу Денгклек берет из мешка $$$j$$$. Результатом всех действий назовем число $$$|w_1 - w_2| + |w_2 - w_3|$$$, где $$$|x|$$$ — модуль числа $$$x$$$.

Известно, что Денгклек будет брать кубики таким образом, чтобы минимизировать результат. Чему равен максимально возможный результат, если Пак Чанек раскладывает кубики оптимально?

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

Каждый тест содержит несколько наборов входных данных. Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$) — количество наборов. Следующие строки содержат описание каждого набора.

Первая строка каждого набора входных данных содержит целое число $$$n$$$ ($$$3 \leq n \leq 2 \cdot 10^5$$$) — количество кубиков.

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

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

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

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

Пример
Входные данные
3
5
3 1 5 2 3
4
17 8 19 45
8
265 265 265 265 265 265 265 265
Выходные данные
6
63
0
Примечание

В первом наборе входных данные, один из вариантов получить итоговый результат, равный $$$6$$$, выглядит следующим образом:

  • Положить кубики $$$1$$$, $$$4$$$, и $$$5$$$ в мешок $$$1$$$.
  • Положить кубик $$$3$$$ в мешок $$$2$$$.
  • Положить кубик $$$2$$$ в мешок $$$3$$$.

Если Пак Чанек разложит кубики таким образом, то Денгклек может взять кубики следующим образом:

  • Взять кубик $$$5$$$ из мешка $$$1$$$.
  • Взять кубик $$$3$$$ из мешка $$$2$$$.
  • Взять кубик $$$2$$$ из мешка $$$3$$$.

Результат равен $$$|a_5 - a_3| + |a_3 - a_2| = |3 - 5| + |5 - 1| = 6$$$. Можно показать, что Бу Денгклек не может получить меньший результат при таком распределении кубиков.

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