CF2018E2 Complex Segments (Hard Version)

[Ken Arai - COMPLEX](https://soundcloud.com/diatomichail2/complex) ⠀ This is the hard version of the problem. In this version, the constraints on $ n $ and the time limit are higher. You can make hacks only if both versions of the problem are solved. A set of (closed) segments is complex if it can be partitioned into some subsets such that - all the subsets have the same size; and - a pair of segments intersects if and only if the two segments are in the same subset. You are given $ n $ segments $ [l_1, r_1], [l_2, r_2], \ldots, [l_n, r_n] $ . Find the maximum size of a complex subset of these segments.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^3 $ ). The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1 \le n \le 3 \cdot 10^5 $ ) — the number of segments. The second line of each test case contains $ n $ integers $ l_1, l_2, \ldots, l_n $ ( $ 1 \le l_i \le 2n $ ) — the left endpoints of the segments. The third line of each test case contains $ n $ integers $ r_1, r_2, \ldots, r_n $ ( $ l_i \leq r_i \le 2n $ ) — the right endpoints of the segments. It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 3 \cdot 10^5 $ .

For each test case, output a single integer: the maximum size of a complex subset of the given segments.

In the first test case, all pairs of segments intersect, therefore it is optimal to form a single group containing all of the three segments. In the second test case, there is no valid partition for all of the five segments. A valid partition with four segments is the following: $ \{\{ [1, 5], [2, 4] \}, \{ [6, 9], [8, 10] \}\} $ . In the third test case, it is optimal to make a single group containing all the segments except the second.