write a go solution for Description:
This is the hard version of a problem. The only difference between an easy and a hard version is the constraints on t and n. You can make hacks only if both versions of the problem are solved.

Arthur is giving a lesson to his famous 2n knights. Like any other students, they're sitting at the desks in pairs, but out of habit in a circle. The knight 2i-1 is sitting at the desk with the knight 2i.

Each knight has intelligence, which can be measured by an integer. Let's denote the intelligence of the i-th knight as a_i. Arthur wants the maximal difference in total intelligence over all pairs of desks to be as small as possible. More formally, he wants to minimize maxlimits_1<=i<=n(a_2i-1+a_2i)-minlimits_1<=i<=n(a_2i-1+a_2i).

However, the Code of Chivalry only allows swapping the opposite knights in the circle, i.e., Arthur can simultaneously perform a_i:=a_i+n, a_i+n:=a_i for any 1<=i<=n. Arthur can make any number of such swaps. What is the best result he can achieve?

Input Format:
Each test consists of several test cases. The first line contains a single integer t (1<=t<=10,000) — the number of test cases. It is followed by descriptions of the test cases.

The first line of each test case contains a single integer n (1<=n<=100,000) — the number of desks.

The second line consists of 2n integers a_1,a_2,ldots,a_2n (1<=a_i<=10^9) — the intelligence values of the knights.

It is guaranteed that the sum of n over all test cases does not exceed 100,000.

Output Format:
For each test case, output a single line containing one integer — the minimal difference Arthur can achieve.

Note:
In the first test case, Arthur can swap the second and the fourth knights. Then the total intelligence at both desks will be 10.

In the third test case, Arthur can make 0 operations, which will result in the total intelligence of 11 at each of the desks.

In the fourth test case, Arthur can swap knights with indices 2 and 5 and achieve the difference of 2. It can be proven that he cannot improve his result any further.. Output only the code with no comments, explanation, or additional text.