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 $2 n$ knights. Like any other students, they're sitting at the desks in pairs, but out of habit in a circle. The knight $2 i - 1$ is sitting at the desk with the knight $2 i$.

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 $\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})$.

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 \le i \le n$. Arthur can make any number of such swaps. What is the best result he can achieve?

Each test consists of several test cases. The first line contains a single integer $t$ ($1 \le t \le 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 \le n \le 100\,000$) — the number of desks.

The second line consists of $2n$ integers $a_1, a_2, \ldots, a_{2 n}$ ($1 \le a_i \le 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$.

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