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 <= i <= n} (a_{2 i - 1} + a_{2 i}) - min limits_{1 <= i <= 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 <= i <= 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 <= 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_{2 n} ( 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 . For each test case, output a single line containing one integer -- the minimal difference Arthur can achieve. 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