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 < 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$ ).