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