这是问题的困难版本。简单版本和困难版本之间的唯一区别是对 $$$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})$$$。
然而,《骑士守则》只允许交换圈内相对的骑士,即亚瑟可以同时对任意 $$$1 \le i \le n$$$ 执行$$$a_i := a_{i + n}$$$、$$$a_{i + n} := a_i$$$。亚瑟可以进行任意数量的此类交换。他能达到的最好结果是什么?
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$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$$$。
输出
对于每个测试用例,输出一行包含一个整数 - Arthur 可以实现的最小差异。
示例
输入 #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
输出 #1
0 0 0 2 4
注意
在第一个测试用例中,亚瑟可以交换第二个和第四个骑士。那么两个办公桌上的总情报将为$$$10$$$。
在第三个测试用例中,Arthur 可以进行 $$$0$$$ 操作,这将导致每个办公桌的总情报为 $$$11$$$。
在第四个测试用例中,Arthur 可以交换索引为 $$$2$$$ 和 $$$5$$$ 的骑士,并获得 $$$2$$$ 的差异。可以证明他的成绩已经无法再提高了。