灯泡（困难版）

• 时间限制：3 秒
• 内存限制：512 MiB

题目描述

有 $2n$ 个灯泡排成一行。每个灯泡的颜色是 $1$ 到 $n$ 中的一个，每种颜色恰好出现两次。最初所有灯泡都关闭，你需要选择一个集合 $S$，将其中灯泡初始打开。

此后可按任意顺序执行任意次操作：

• 若同色的两盏灯恰有一盏打开，则打开另一盏；
• 若位置 $i,k$ 的两盏同色灯均已打开，则可打开任意满足 $i<j<k$ 的灯泡 $j$。

选择 $S$ 使所有灯泡最终都能打开。求 $|S|$ 的最小值，以及达到最小值的集合 $S$ 的数量。方案数对 $998244353$ 取模。

输入格式

第一行一个整数 $t$，表示测试用例数量。

每个测试用例第一行一个整数 $n$，第二行给出 $2n$ 个整数 $c_1,c_2,\ldots,c_{2n}$。每种颜色 $1,2,\ldots,n$ 恰好出现两次。

输出格式

对每个测试用例输出两个整数：最小的 $|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

样例输出 1

2 4
1 2
1 4
2 8

数据范围

• $1\le t\le10^4$；
• $2\le n\le2\times10^5$；
• $1\le c_i\le n$，每种颜色恰好出现两次；
• 单个输入文件内所有测试用例的 $n$ 之和不超过 $2\times10^5$。