E2. Позвольте мне преподать вам урок (сложная версия)
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Артур проводит урок для своих знаменитых $$$2 n$$$ рыцарей. Как и все другие студенты, они сидят за партами парами, но по привычке по кругу. Рыцарь $$$2 i - 1$$$ сидит за партой с рыцарем $$$2 i$$$.

Каждый рыцарь имеет интеллект, который можно измерить целым числом. Обозначим интеллект $$$i$$$-го рыцаря как $$$a_i$$$. Артур хочет, чтобы максимальная разница в общем интеллекте по всем парам парт была как можно меньше. Более формально, он хочет минимизировать $$$\max\limits_{1 \le i \le n} (a_{2 i - 1} + a_{2 i}) - \min\limits_{1 \le i \le n} (a_{2 i - 1} + a_{2 i})$$$.

Однако рыцарский кодекс позволяет менять местами только противоположных рыцарей в круге, т.е. Артур может одновременно выполнять $$$a_i := a_{i + n}$$$, $$$a_{i + n} := a_i$$$ для любого $$$1 \le i \le n$$$. Артур может делать любое количество таких обменов. Какой наилучший результат он может себе обеспечить?

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 10\,000$$$) — количество наборов входных данных. За ним следуют описания наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 100\,000$$$) — количество парт.

Вторая строка состоит из $$$2n$$$ целых чисел $$$a_1, a_2, \ldots, a_{2 n}$$$ ($$$1 \le a_i \le 10^9$$$) — значения интеллекта рыцарей.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$100\,000$$$.

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

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

Пример
Входные данные
5
2
6 6 4 4
1
10 17
3
1 10 1 10 1 10
3
3 3 4 5 5 4
5
1 2 3 4 5 6 7 8 9 10
Выходные данные
0
0
0
2
4
Примечание

В первом наборе входных данных Артур может поменять местами второго и четвертого рыцарей. Тогда общий интеллект на обеих партах составит $$$10$$$.

В третьем наборе входных данных Артур может сделать $$$0$$$ операций, что приведет к общему интеллекту $$$11$$$ за каждой из парт.

В четвертом наборе входных данных Артур может поменять местами рыцарей с индексами $$$2$$$ и $$$5$$$ и достичь разницы $$$2$$$. Можно доказать, что он не может улучшить свой результат дальше.