Codeforces Round 961 (Div. 2) |
---|
Finished |
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.
526 6 4 4110 1731 10 1 10 1 1033 3 4 5 5 451 2 3 4 5 6 7 8 9 10
0 0 0 2 4
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.
Name |
---|