给定一个序列 $$$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)$$$ 的最大值。
示例
输入复制
721 2 3 435 5 5 5 5 543 3 7 6 3 7 8 722 2 2 261 2 3 4 5 4 1 4 1 5 4 641 2 1 2 1 2 1 259 9 9 7 7 7 9 7 7 7
输出复制
4240842
注意
对于第一个测试用例:
- 我们可以将数组划分为 $$$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$$$。