Codeforces Round 916 (Div. 3) |
---|
Finished |
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:
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 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:
422 2 1 121 2 2 121 2 1 253 4 4 5 3 1 1 5 2 2
2 4 1 2 1 4 2 8
Name |
---|