← 返回题目列表

Codeforces · 2158/B

B. 分裂

中文机器翻译题面 查看原题

给定一个序列 $$$a$$$,其中包含 $$$2n$$$ 整数。令 $$$f(b)$$$ 表示序列 $$$b$$$ 中出现奇数次的不同元素的数量。您需要将给定数组拆分为两个不相交的子序列 $$$p$$$ 和 $$$q$$$,每个子序列的大小为 $$$n$$$,以便最大化 $$$f(p) + f(q)$$$。输出 最大 值。

序列 $$$a$$$ 是序列 $$$b$$$ 的子序列,如果 $$$a$$$ 可以通过从任意位置删除几个(可能是零个或全部)元素从 $$$b$$$ 获得。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$)。

第二行包含 $$$2n$$$ 整数 $$$a_1,a_2,\ldots,a_{2n}$$$ ($$$1 \le a_i \le 2n$$$) — 序列 $$$a$$$ 的元素。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,打印一行。

您必须打印可以达到的 $$$f(p) + f(q)$$$ 的最大值。

示例

输入
复制

7
2
1 2 3 4
3
5 5 5 5 5 5
4
3 3 7 6 3 7 8 7
2
2 2 2 2
6
1 2 3 4 5 4 1 4 1 5 4 6
4
1 2 1 2 1 2 1 2
5
9 9 9 7 7 7 9 7 7 7

输出
复制

4
2
4
0
8
4
2

注意

对于第一个测试用例:

  • 我们可以将数组划分为 $$$p = [1, 3]$$$ 和 $$$q = [2, 4]$$$。
  • 这样,$$$f(p) = 2$$$ 和 $$$f(q) = 2$$$ 因为两者都有两个具有奇数频率的不同元素。

对于第二个测试用例:

  • 我们可以对数组进行划分,使得 $$$p = [5, 5, 5]$$$ 和 $$$q = [5, 5, 5]$$$。
  • 这样,$$$f(p) = 1$$$ 和 $$$f(q) = 1$$$。

对于第五个测试用例:

  • 我们可以对数组进行划分,使得 $$$p = [1, 2, 3, 4, 5, 6]$$$ 和 $$$q = [4, 1, 4, 1, 5, 4]$$$。
  • 这样,$$$f(p) = 6$$$ 和 $$$f(q) = 2$$$。