310966: CF1914G2. Light Bulbs (Hard Version)

G2. Light Bulbs (Hard Version)time limit per test3 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard output

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

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

ExampleInput

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

Output

2 4
1 2
1 4
2 8

题目大意：

这个问题的简单版本和困难版本只在关于 $ n $ 的限制上有所不同。在困难版本中，所有测试用例的 $ n $ 值的总和不超过 $ 2 \times 10^5 $。此外，单个测试用例中 $ n $ 的值没有额外的限制。

有 $ 2n $ 个灯泡排成一行。每个灯泡有一个从 $ 1 $ 到 $ n $ 的颜色（每种颜色恰好有两个灯泡）。

最初，所有灯泡都是关闭的。你选择一个灯泡集合 $ S $，最初打开这些灯泡。在此之后，你可以按任何顺序、任意次数执行以下操作：

1. 选择两个颜色相同的灯泡 $ i $ 和 $ j $，其中恰好有一个是开的，然后打开另一个；
2. 选择三个灯泡 $ i, j, k $，使得灯泡 $ i $ 和 $ k $ 都是开的并且颜色相同，灯泡 $ j $ 位于它们之间（$ i < j < k $），然后打开灯泡 $ j $。

你想选择一个灯泡集合 $ S $，你最初打开这些灯泡，以便通过执行上述操作，可以确保所有灯泡都被打开。

计算两个数字：

1. 初始打开的集合 $ S $ 的最小大小；
2. 最小大小的集合 $ S $ 的数量（取模 $ 998244353 $）。

输入输出数据格式：

输入：

第一行包含一个整数 $ t $（$ 1 \le t \le 10^4 $）——测试用例的数量。然后是测试用例的描述。

每个测试用例的第一行包含一个整数 $ n $（$ 2 \le n \le 2 \times 10^5 $）——灯泡对的数量。

每个测试用例的第二行包含 $ 2n $ 个整数 $ c_1, c_2, \dots, c_{2n} $（$ 1 \le c_i \le n $），其中 $ c_i $ 是第 $ i $ 个灯泡的颜色。对于从 $ 1 $ 到 $ n $ 的每个颜色，恰好有两个灯泡具有这种颜色。

输入的附加限制：所有测试用例的 $ n $ 值的总和不超过 $ 2 \times 10^5 $。

输出：

对于每个测试用例，输出两个整数：

1. 初始打开的集合 $ S $ 的最小大小；
2. 最小大小的集合 $ S $ 的数量（取模 $ 998244353 $）。题目大意： 这个问题的简单版本和困难版本只在关于 $ n $ 的限制上有所不同。在困难版本中，所有测试用例的 $ n $ 值的总和不超过 $ 2 \times 10^5 $。此外，单个测试用例中 $ n $ 的值没有额外的限制。 有 $ 2n $ 个灯泡排成一行。每个灯泡有一个从 $ 1 $ 到 $ n $ 的颜色（每种颜色恰好有两个灯泡）。 最初，所有灯泡都是关闭的。你选择一个灯泡集合 $ S $，最初打开这些灯泡。在此之后，你可以按任何顺序、任意次数执行以下操作： 1. 选择两个颜色相同的灯泡 $ i $ 和 $ j $，其中恰好有一个是开的，然后打开另一个； 2. 选择三个灯泡 $ i, j, k $，使得灯泡 $ i $ 和 $ k $ 都是开的并且颜色相同，灯泡 $ j $ 位于它们之间（$ i < j < k $），然后打开灯泡 $ j $。 你想选择一个灯泡集合 $ S $，你最初打开这些灯泡，以便通过执行上述操作，可以确保所有灯泡都被打开。 计算两个数字： 1. 初始打开的集合 $ S $ 的最小大小； 2. 最小大小的集合 $ S $ 的数量（取模 $ 998244353 $）。 输入输出数据格式： 输入： 第一行包含一个整数 $ t $（$ 1 \le t \le 10^4 $）——测试用例的数量。然后是测试用例的描述。 每个测试用例的第一行包含一个整数 $ n $（$ 2 \le n \le 2 \times 10^5 $）——灯泡对的数量。 每个测试用例的第二行包含 $ 2n $ 个整数 $ c_1, c_2, \dots, c_{2n} $（$ 1 \le c_i \le n $），其中 $ c_i $ 是第 $ i $ 个灯泡的颜色。对于从 $ 1 $ 到 $ n $ 的每个颜色，恰好有两个灯泡具有这种颜色。 输入的附加限制：所有测试用例的 $ n $ 值的总和不超过 $ 2 \times 10^5 $。 输出： 对于每个测试用例，输出两个整数： 1. 初始打开的集合 $ S $ 的最小大小； 2. 最小大小的集合 $ S $ 的数量（取模 $ 998244353 $）。