CF2018E2 Complex Segments (Hard Version)

这是这个问题的困难版本。在这个版本中， $n$ 的范围和时间限制都变高了。 当一个区间的集合可以被分割成一些子集并满足以下条件时，这个集合是复杂的： - 所有的子集的大小相同 - 当且仅当两个区间在同一子集内时，这两个区间相交。 $t$ 组数据，每组数据给你一个集合包含 $n$ 个区间 $[l_1, r_1], [l_2, r_2], \dots, [l_n, r_n]$。求出最大的子集满足其为复杂的，输出这个集合的大小。

第一行输入数据个数 $t(1 \le t \le 10^3)$。 每个数据的第一行包含一个整数 $n(1 \le n \le 3 \cdot 10^5)$，集合的区间个数。 每个数据的第二行包含 $n$ 个整数 $l_1, l_2, \ldots, l_n(1 \le l_i \le 2n)$，分别表示这 $n$ 个区间的左端点。 每个数据的第三行包含 $n$ 个整数 $r_1, r_2, \ldots, r_n(l_i \leq r_i \le 2n)$，分别表示这 $n$ 个区间的右端点。 保证所有数据 $n$ 的总和不超过 $3 \cdot 10^5$。

对于每个数据输出一行表示最大的复杂的子集的大小。

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.