Это сложная версия задачи. Единственное отличие между простой и сложной версиями заключается в ограничениях на \(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\). Артур может делать любое количество таких обменов. Какой наилучший результат он может себе обеспечить?
Выходные данные
Для каждого набора входных данных выведите одну строку, содержащую одно целое число — минимальная разница, которую Артур может достичь.
Примечание
В первом наборе входных данных Артур может поменять местами второго и четвертого рыцарей. Тогда общий интеллект на обеих партах составит \(10\).
В третьем наборе входных данных Артур может сделать \(0\) операций, что приведет к общему интеллекту \(11\) за каждой из парт.
В четвертом наборе входных данных Артур может поменять местами рыцарей с индексами \(2\) и \(5\) и достичь разницы \(2\). Можно доказать, что он не может улучшить свой результат дальше.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|