← 返回题目列表

Codeforces · 1995/E2

E2. 让我教你一课(困难版)

中文机器翻译题面 查看原题

这是问题的困难版本。简单版本和困难版本之间的唯一区别是对 $$$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$$$ 的差异。可以证明他的成绩已经无法再提高了。