CF1995E2.Let Me Teach You a Lesson (Hard Version)

这是一个难度较高的版本。与简单版本的唯一区别在于 $t$ 和 $n$ 的约束条件。只有当你同时解决了两个版本的问题时，才能进行 hack。

Arthur 正在给他著名的 $2n$ 位骑士上课。和其他学生一样，他们成对坐在桌前，但出于习惯，他们是围成一个圆圈坐的。第 $2i-1$ 位骑士和第 $2i$ 位骑士坐在同一张桌子上。

每位骑士都有一个智力值，用整数表示。我们用 $a_i$ 表示第 $i$ 位骑士的智力值。Arthur 希望所有桌子的总智力值的最大差值尽可能小。更正式地说，他希望最小化 $\max\limits_{1 \le i \le n} (a_{2i-1} + a_{2i}) - \min\limits_{1 \le i \le n} (a_{2i-1} + a_{2i})$。

然而，骑士守则只允许交换圆圈中相对位置的骑士，也就是说，Arthur 可以同时执行 $a_i := a_{i+n}$，$a_{i+n} := a_i$，其中 $1 \le i \le n$。Arthur 可以进行任意次数这样的交换。请问他能达到的最小差值是多少？

每组测试数据包含若干个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10\,000$），表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$（$1 \le n \le 100\,000$），表示桌子的数量。

第二行包含 $2n$ 个整数 $a_1, a_2, \ldots, a_{2n}$（$1 \le a_i \le 10^9$），表示每位骑士的智力值。

保证所有测试用例中 $n$ 的总和不超过 $100\,000$。

对于每个测试用例，输出一行一个整数，表示 Arthur 能达到的最小差值。

在第一个测试用例中，Arthur 可以交换第 $2$ 位和第 $4$ 位骑士。这样两张桌子的总智力值都是 $10$。

在第三个测试用例中，Arthur 不需要进行任何操作，每张桌子的总智力值都是 $11$。

在第四个测试用例中，Arthur 可以交换编号为 $2$ 和 $5$ 的骑士，得到的差值为 $2$。可以证明无法取得更优的结果。

由 ChatGPT 4.1 翻译