CF1914G2 Light Bulbs (Hard Version)

这道题的简单版和困难版仅在 $ 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 $ 取模）。

翻译由 [yanrs1019](https://www.luogu.com.cn/user/1304706) 提供。