Light Bulbs (Hard Version)
Description
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 < j < 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$).
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$.
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$).
Input
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$.
Output
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$).
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