G2. Лампочки (сложная версия)
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Простая и сложная версии этой задачи отличаются друг от друга только ограничениями на $$$n$$$. В сложной версии сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$. Кроме того, никаких дополнительных ограничений на значение $$$n$$$ в одиночном наборе входных данных нет.

В ряд расположены $$$2n$$$ лампочек. У каждой лампочки есть цвет от $$$1$$$ до $$$n$$$ (ровно по две лампочки каждого цвета).

Изначально все лампочки выключены. Вы выбираете некоторое множество лампочек $$$S$$$, которое вы изначально включите. После этого вы можете выполнять следующие операции в любом порядке любое количество раз:

  • выбрать две лампочки $$$i$$$ и $$$j$$$ одинакового цвета, ровно одна из которых включена, и включить вторую из них;
  • выбрать три лампочки $$$i, j, k$$$, такие, что обе лампочки $$$i$$$ и $$$k$$$ включены и имеют одинаковый цвет, а лампочка $$$j$$$ находится между ними ($$$i < j < k$$$), и включить лампочку $$$j$$$.

Вы хотите выбрать такое множество лампочек $$$S$$$, которые вы изначально включаете, чтобы путем выполнения описанных операций можно было добиться того, чтобы все лампочки оказались включены.

Посчитайте два числа:

  • минимальный размер множества $$$S$$$, которое вы изначально включаете;
  • количество множеств $$$S$$$ минимального размера (по модулю $$$998244353$$$).
Входные данные

В первой строке входных данных содержится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следуют описания наборов.

В первой строке каждого набора задано одно целое число $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — количество пар лампочек.

Во второй строке каждого набора заданы $$$2n$$$ целых чисел $$$c_1, c_2, \dots, c_{2n}$$$ ($$$1 \le c_i \le n$$$), где $$$c_i$$$ — цвет $$$i$$$-й лампочки. Для каждого цвета от $$$1$$$ до $$$n$$$ ровно две лампочки имеют этот цвет.

Дополнительное ограничение на входные данные: сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите два целых числа:

  • минимальный размер множества $$$S$$$, которое вы изначально включаете;
  • количество множеств $$$S$$$ минимального размера (по модулю $$$998244353$$$).
Пример
Входные данные
4
2
2 2 1 1
2
1 2 2 1
2
1 2 1 2
5
3 4 4 5 3 1 1 5 2 2
Выходные данные
2 4
1 2
1 4
2 8