CF1914G2.Light Bulbs (Hard Version)

The easy and hard versions of this problem differ only in the constraints on $n$. In the hard version, the sum of values of $n$ over all test cases does not exceed $2 \cdot 10^5$. Furthermore, there are no additional constraints on the value of $n$ in a single test case.

There are $2n$ light bulbs arranged in a row. Each light bulb has a color from $1$ to $n$ (exactly two light bulbs for each color).

Initially, all light bulbs are turned off. You choose a set of light bulbs $S$ that you initially turn on. After that, you can perform the following operations in any order any number of times:

• choose two light bulbs $i$ and $j$ of the same color, exactly one of which is on, and turn on the second one;
• choose three light bulbs $i, j, k$, such that both light bulbs $i$ and $k$ are on and have the same color, and the light bulb $j$ is between them ($i \lt j \lt k$), and turn on the light bulb $j$.

You want to choose a set of light bulbs $S$ that you initially turn on in such a way that by performing the described operations, you can ensure that all light bulbs are turned on.

Calculate two numbers:

• the minimum size of the set $S$ that you initially turn on;
• the number of sets $S$ of minimum size (taken modulo $998244353$).

本题的简单版与困难版仅在 $n$ 的约束条件上有所不同。在困难版中，所有测试用例的 $n$ 值之和不超过 $2 \cdot 10^5$。此外，单个测试用例中对 $n$ 的取值无额外限制。

有 $2n$ 个灯泡排成一行。每个灯泡的颜色为 $1$ 到 $n$ 中的一个整数（每种颜色恰好对应两个灯泡）。

初始时，所有灯泡均处于关闭状态。你需要选定一个灯泡集合 $S$，并将其中所有灯泡初始设为开启状态。此后，你可以以任意顺序、任意次数执行以下两种操作：

• 选择两个同色灯泡 $i$ 和 $j$，其中恰好有一个处于开启状态，并将另一个也开启；
• 选择三个灯泡 $i, j, k$，满足灯泡 $i$ 和 $k$ 均已开启且同色，且灯泡 $j$ 位于它们之间（即 $i \lt j \lt k$），然后将灯泡 $j$ 开启。

你的目标是选择一个初始开启的灯泡集合 $S$，使得通过执行上述操作，最终能确保所有灯泡均被开启。

请计算以下两个数值：

• 初始开启集合 $S$ 的最小可能大小；
• 达到该最小大小的集合 $S$ 的数量（对 $998244353$ 取模）。

The first line of the input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then follow the descriptions of the test cases.

The first line of each test case contains a single integer $n$ ($2 \le n \le 2 \cdot 10^5$) — the number of pairs of light bulbs.

The second line of each test case contains $2n$ integers $c_1, c_2, \dots, c_{2n}$ ($1 \le c_i \le n$), where $c_i$ is the color of the $i$-th light bulb. For each color from $1$ to $n$, exactly two light bulbs have this color.

Additional constraint on the input: the sum of values of $n$ over all test cases does not exceed $2 \cdot 10^5$.

输入的第一行包含一个整数 $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$。

For each test case, output two integers:

• the minimum size of the set $S$ that you initially turn on;
• the number of sets $S$ of minimum size (taken modulo $998244353$).

对每个测试用例，输出两个整数：

• 你最初需要开启的集合 $S$ 的最小大小；
• 大小为该最小值的集合 $S$ 的个数（对 $998244353$ 取模）。