Простая и сложная версии этой задачи отличаются друг от друга только ограничениями на \(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\)).
Выходные данные
Для каждого набора входных данных выведите два целых числа:
- минимальный размер множества \(S\), которое вы изначально включаете;
- количество множеств \(S\) минимального размера (по модулю \(998244353\)).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|