G2. Light Bulbs (Hard Version)
combinatorics; data structures; dfs and similar; dp; graphs; hashing
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\)).