← 返回题目列表

Codeforces · 1506/D

D. 史诗般的转变

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

给定一个数组 $$$a$$$,长度为 $$$n$$$,由整数组成。您可以对数组 $$$a$$$ 应用以下由多个步骤组成的操作零次或多次:

- 在数组 $$$a_i$$$ 和 $$$a_j$$$ 中选择两个不同的数字;
- 从数组中删除第 $$$i$$$ 和第 $$$j$$$ 个元素。

例如,如果 $$$n=6$$$ 且 $$$a=[1, 6, 1, 1, 4, 4]$$$,则可以执行以下操作序列:

- 选择$$$i=1,j=5$$$。数组 $$$a$$$ 等于 $$$[6, 1, 1, 4]$$$;
- 选择$$$i=1,j=2$$$。数组 $$$a$$$ 等于 $$$[1, 4]$$$。

对数组应用一些操作序列后,数组的最小大小是多少?

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$)。然后是 $$$t$$$ 测试用例。

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

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$)。

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

输出

对于每个测试用例,在对其应用一些操作序列后输出数组的最小可能大小。

示例

输入 #1

5
6
1 6 1 1 4 4
2
1 2
2
1 1
5
4 5 4 5 4
6
2 3 2 1 3 1

输出 #1

0
0
2
1
0