给定一个由 $$$n$$$ 整数组成的数组 $$$a$$$。
数组 $$$q_1, q_2, \ldots, q_k$$$ 的中位数是数字 $$$p_{\lceil \frac{k}{2} \rceil}$$$,其中 $$$p$$$ 是按非降序排序的数组 $$$q$$$。例如,数组 $$$[9, 5, 1, 2, 6]$$$ 的中位数是 $$$5$$$,在排序数组 $$$[1, 2, 5, 6, 9]$$$ 中,索引 $$$\lceil \frac{5}{2} \rceil = 3$$$ 处的数字是 $$$5$$$,而数组 $$$[9, 2, 8, 3]$$$ 是 $$$3$$$,就像在排序数组 $$$[2, 3, 8, 9]$$$ 中一样,索引 $$$\lceil \frac{4}{2} \rceil = 2$$$ 处的数字是 $$$3$$$。
您可以选择一个整数 $$$i$$$ ($$$1 \le i \le n$$$) 并在一次操作中将 $$$a_i$$$ 增加 $$$1$$$。
你的任务是找到增加数组中位数所需的最少操作数。
请注意,数组 $$$a$$$ 不一定包含不同的数字。
输入
每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。然后是测试用例的描述。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 数组 $$$a$$$ 的长度。
每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) - 数组 $$$a$$$。
保证所有测试用例的 $$$n$$$ 值之和不超过 $$$2 \cdot 10^5$$$。
输出
对于每个测试用例,输出一个整数 - 增加数组中位数所需的最少操作数。
示例
输入 #1
8 3 2 2 8 4 7 3 3 1 1 1000000000 5 5 5 5 4 5 6 2 1 2 3 1 4 2 1 2 2 1 1 4 5 5 5 5
输出 #1
1 2 1 3 2 1 2 3
注意
在第一个测试用例中,可以对第一个数字进行一次操作,得到数组 $$$[3, 2, 8]$$$,该数组的中位数为 $$$3$$$,因为它是非递减排序数组 $$$[2, 3, 8]$$$ 中索引 $$$\lceil \frac{3}{2} \rceil = 2$$$ 处的数字。原始数组 $$$[2, 2, 8]$$$ 的中位数是 $$$2$$$,因为它是非递减排序数组 $$$[2, 2, 8]$$$ 中索引 $$$\lceil \frac{3}{2} \rceil = 2$$$ 处的数字。因此,仅在一次操作中中位数就增加了 ($$$3 > 2$$$)。
在第四个测试用例中,对索引 $$$1, 2, 3$$$ 处的每个数字进行一次操作,得到数组 $$$[6, 6, 6, 4, 5]$$$,该数组的中位数为 $$$6$$$,因为它是索引 $$$\lceil \frac{5}{2} \rceil = 3$$$ 处的数字非递减排序数组 $$$[4, 5, 6, 6, 6]$$$。原始数组 $$$[5, 5, 5, 4, 5]$$$ 的中位数是 $$$5$$$,因为它是非递减排序数组 $$$[4, 5, 5, 5, 5]$$$ 中索引 $$$\lceil \frac{5}{2} \rceil = 2$$$ 处的数字。因此,三项手术的中位数有所增加 ($$$6 > 5$$$)。可以证明这是最小可能的操作数。
在第五个测试用例中,对索引 $$$1, 3$$$ 处的每个数字进行一次操作,得到数组 $$$[3, 1, 3, 3, 1, 4]$$$,该数组的中位数为 $$$3$$$,因为它是索引 $$$\lceil \frac{6}{2} \rceil = 3$$$ 处的数字非递减排序数组 $$$[1, 1, 3, 3, 3, 4]$$$。原始数组 $$$[2, 1, 2, 3, 1, 4]$$$ 的中位数是 $$$2$$$,因为它是非递减排序数组 $$$[1, 1, 2, 2, 3, 4]$$$ 中索引 $$$\lceil \frac{6}{2} \rceil = 3$$$ 处的数字。因此,两次手术的中位数增加了 ($$$3 > 2$$$)。可以证明这是最小可能的操作数。