Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов. ×

E2. Сложные отрезки (сложная версия)
ограничение по времени на тест
13 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Ken Arai - COMPLEX
⠀

Это сложная версия задачи. В этой версии ограничения на $$$n$$$ и ограничение по времени выше. Вы можете совершать взломы только в том случае, если решены обе версии задачи.

Назовём множество (замкнутых) отрезков сложным, если оно может быть разбито на некоторые подмножества так, что

  • все подмножества имеют одинаковый размер; и
  • пара отрезков пересекается тогда и только тогда, когда эти два отрезка находятся в одном и том же подмножестве.

Вам даны $$$n$$$ отрезков $$$[l_1, r_1], [l_2, r_2], \ldots, [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$$$ целых чисел $$$r_1, r_2, \ldots, r_n$$$ ($$$l_i \leq r_i \le 2n$$$) — правые концы отрезков.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$3 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите одно целое число: максимальный размер сложного подмножества заданных отрезков.

Пример
Входные данные
3
3
1 2 3
5 4 6
5
1 2 3 6 8
5 4 7 9 10
5
3 1 4 1 5
7 2 6 5 10
Выходные данные
3
4
4
Примечание

В первом наборе входных данных все пары отрезков пересекаются, поэтому оптимально сформировать одну группу, содержащую все три отрезка.

Во втором наборе входных данных не существует подходящего разбиения для всех пяти отрезков. Корректное разбиение с четырьмя отрезками выглядит следующим образом: $$$\{\{ [1, 5], [2, 4] \}, \{ [6, 9], [8, 10] \}\}$$$.

В третьем наборе входных данных оптимально составить одну группу, содержащую все отрезки, кроме второго.