CF2158B Split

You are given a sequence $ a $ containing $ 2n $ integers. Let $ f(b) $ denote the number of distinct elements with an odd number of occurrences in sequence $ b $ . You need to split the given array into two disjoint subsequences $ p $ and $ q $ , each of size $ n $ , such that $ f(p) + f(q) $ is maximized. Output the maximum value. A sequence $ a $ is a subsequence of a sequence $ b $ if $ a $ can be obtained from $ b $ by the deletion of several (possibly, zero or all) element from arbitrary positions.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 10^4 $ ). The description of the test cases follows. The first line of each test case contains an integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ). The second line contains $ 2n $ integers $ a_1,a_2,\ldots,a_{2n} $ ( $ 1 \le a_i \le 2n $ ) — the elements of sequence $ a $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

For each test case, print one line. You have to print the maximum value of $ f(p) + f(q) $ that can be achieved.

For the first test case: - We can divide the array such that $ p = [1, 3] $ and $ q = [2, 4] $ . - This way, $ f(p) = 2 $ and $ f(q) = 2 $ since both have two distinct elements with odd frequency. For the second test case: - We can divide the array such that $ p = [5, 5, 5] $ and $ q = [5, 5, 5] $ . - This way, $ f(p) = 1 $ and $ f(q) = 1 $ . For the fifth test case: - We can divide the array such that $ p = [1, 2, 3, 4, 5, 6] $ and $ q = [4, 1, 4, 1, 5, 4] $ . - This way, $ f(p) = 6 $ and $ f(q) = 2 $ .