311184: CF1946A. Median of an Array

A. Median of an Arraytime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

You are given an array $a$ of $n$ integers.

The median of an array $q_1, q_2, \ldots, q_k$ is the number $p_{\lceil \frac{k}{2} \rceil}$, where $p$ is the array $q$ sorted in non-decreasing order. For example, the median of the array $[9, 5, 1, 2, 6]$ is $5$, as in the sorted array $[1, 2, 5, 6, 9]$, the number at index $\lceil \frac{5}{2} \rceil = 3$ is $5$, and the median of the array $[9, 2, 8, 3]$ is $3$, as in the sorted array $[2, 3, 8, 9]$, the number at index $\lceil \frac{4}{2} \rceil = 2$ is $3$.

You are allowed to choose an integer $i$ ($1 \le i \le n$) and increase $a_i$ by $1$ in one operation.

Your task is to find the minimum number of operations required to increase the median of the array.

Note that the array $a$ may not necessarily contain distinct numbers.

Input

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. Then follows the description of the test cases.

The first line of each test case contains a single integer $n$ ($1 \le n \le 10^5$) — the length of the array $a$.

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$) — the array $a$.

It is guaranteed that the sum of the values of $n$ over all test cases does not exceed $2 \cdot 10^5$.

Output

For each test case, output a single integer — the minimum number of operations required to increase the median of the array.

ExampleInput

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

Output

1
2
1
3
2
1
2
3

Note

In the first test case, you can apply one operation to the first number and obtain the array $[3, 2, 8]$, the median of this array is $3$, as it is the number at index $\lceil \frac{3}{2} \rceil = 2$ in the non-decreasing sorted array $[2, 3, 8]$. The median of the original array $[2, 2, 8]$ is $2$, as it is the number at index $\lceil \frac{3}{2} \rceil = 2$ in the non-decreasing sorted array $[2, 2, 8]$. Thus, the median increased ($3 > 2$) in just one operation.

In the fourth test case, you can apply one operation to each of the numbers at indices $1, 2, 3$ and obtain the array $[6, 6, 6, 4, 5]$, the median of this array is $6$, as it is the number at index $\lceil \frac{5}{2} \rceil = 3$ in the non-decreasing sorted array $[4, 5, 6, 6, 6]$. The median of the original array $[5, 5, 5, 4, 5]$ is $5$, as it is the number at index $\lceil \frac{5}{2} \rceil = 2$ in the non-decreasing sorted array $[4, 5, 5, 5, 5]$. Thus, the median increased ($6 > 5$) in three operations. It can be shown that this is the minimum possible number of operations.

In the fifth test case, you can apply one operation to each of the numbers at indices $1, 3$ and obtain the array $[3, 1, 3, 3, 1, 4]$, the median of this array is $3$, as it is the number at index $\lceil \frac{6}{2} \rceil = 3$ in the non-decreasing sorted array $[1, 1, 3, 3, 3, 4]$. The median of the original array $[2, 1, 2, 3, 1, 4]$ is $2$, as it is the number at index $\lceil \frac{6}{2} \rceil = 3$ in the non-decreasing sorted array $[1, 1, 2, 2, 3, 4]$. Thus, the median increased ($3 > 2$) in two operations. It can be shown that this is the minimum possible number of operations.

题目大意：
给定一个由n个整数组成的数组a。数组q的中位数是数组q按非递减顺序排序后索引为p_⌈k/2⌉的数字，其中p是排序后的数组q。例如，数组[9, 5, 1, 2, 6]的中位数是5，因为在排序后的数组[1, 2, 5, 6, 9]中，索引⌈5/2⌉=3的数字是5，数组[9, 2, 8, 3]的中位数是3，因为在排序后的数组[2, 3, 8, 9]中，索引⌈4/2⌉=2的数字是3。可以在一次操作中选择一个整数i（1≤i≤n）并将a_i增加1。任务是找到将数组的中位数增加所需的最小操作数。注意，数组a可能不一定包含不同的数字。

输入数据格式：
每个测试用例由多个测试组成。第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。接下来是测试用例的描述。
每个测试用例的第一行包含一个整数n（1≤n≤10^5）——数组a的长度。
每个测试用例的第二行包含n个整数a_1, a_2, ..., a_n（1≤a_i≤10^9）——数组a。
保证所有测试用例的n值之和不超过2×10^5。

输出数据格式：
对于每个测试用例，输出一个整数——将数组的中位数增加所需的最小操作数。

示例输入输出：
输入：
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
2
1
3
2
1
2
3

注意：
在第一个测试用例中，可以对第一个数字应用一次操作，得到数组[3, 2, 8]，该数组的中位数是3，因为在非递减排序数组[2, 3, 8]中，索引⌈3/2⌉=2的数字是3。原始数组[2, 2, 8]的中位数是2，因为在非递减排序数组[2, 2, 8]中，索引⌈3/2⌉=2的数字是2。因此，中位数在仅一次操作后增加（3>2）。
在第四个测试用例中，可以对索引1、2、3处的每个数字应用一次操作，得到数组[6, 6, 6, 4, 5]，该数组的中位数是6，因为在非递减排序数组[4, 5, 6, 6, 6]中，索引⌈5/2⌉=3的数字是6。原始数组[5, 5, 5, 4, 5]的中位数是5，因为在非递减排序数组[4, 5, 5, 5, 5]中，索引⌈5/2⌉=2的数字是5。因此，中位数在三次操作后增加（6>5）。可以证明这是可能的最小操作数。
在第五个测试用例中，可以对索引1、3处的每个数字应用一次操作，得到数组[3, 1, 3, 3, 1, 4]，该数组的中位数是3，因为在非递减排序数组[1, 1, 3, 3, 3, 4]中，索引⌈6/2⌉=3的数字是3。原始数组[2, 1, 2, 3, 1, 4]的中位数是2，因为在非递减排序数组[1, 1, 2, 2, 3, 4]中，索引⌈6/2⌉=3的数字是2。因此，中位数在两次操作后增加（3>2）。可以证明这是可能的最小操作数。题目大意： 给定一个由n个整数组成的数组a。数组q的中位数是数组q按非递减顺序排序后索引为p_⌈k/2⌉的数字，其中p是排序后的数组q。例如，数组[9, 5, 1, 2, 6]的中位数是5，因为在排序后的数组[1, 2, 5, 6, 9]中，索引⌈5/2⌉=3的数字是5，数组[9, 2, 8, 3]的中位数是3，因为在排序后的数组[2, 3, 8, 9]中，索引⌈4/2⌉=2的数字是3。可以在一次操作中选择一个整数i（1≤i≤n）并将a_i增加1。任务是找到将数组的中位数增加所需的最小操作数。注意，数组a可能不一定包含不同的数字。 输入数据格式： 每个测试用例由多个测试组成。第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。接下来是测试用例的描述。 每个测试用例的第一行包含一个整数n（1≤n≤10^5）——数组a的长度。 每个测试用例的第二行包含n个整数a_1, a_2, ..., a_n（1≤a_i≤10^9）——数组a。 保证所有测试用例的n值之和不超过2×10^5。 输出数据格式： 对于每个测试用例，输出一个整数——将数组的中位数增加所需的最小操作数。 示例输入输出： 输入： 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 2 1 3 2 1 2 3 注意： 在第一个测试用例中，可以对第一个数字应用一次操作，得到数组[3, 2, 8]，该数组的中位数是3，因为在非递减排序数组[2, 3, 8]中，索引⌈3/2⌉=2的数字是3。原始数组[2, 2, 8]的中位数是2，因为在非递减排序数组[2, 2, 8]中，索引⌈3/2⌉=2的数字是2。因此，中位数在仅一次操作后增加（3>2）。 在第四个测试用例中，可以对索引1、2、3处的每个数字应用一次操作，得到数组[6, 6, 6, 4, 5]，该数组的中位数是6，因为在非递减排序数组[4, 5, 6, 6, 6]中，索引⌈5/2⌉=3的数字是6。原始数组[5, 5, 5, 4, 5]的中位数是5，因为在非递减排序数组[4, 5, 5, 5, 5]中，索引⌈5/2⌉=2的数字是5。因此，中位数在三次操作后增加（6>5）。可以证明这是可能的最小操作数。 在第五个测试用例中，可以对索引1、3处的每个数字应用一次操作，得到数组[3, 1, 3, 3, 1, 4]，该数组的中位数是3，因为在非递减排序数组[1, 1, 3, 3, 3, 4]中，索引⌈6/2⌉=3的数字是3。原始数组[2, 1, 2, 3, 1, 4]的中位数是2，因为在非递减排序数组[1, 1, 2, 2, 3, 4]中，索引⌈6/2⌉=3的数字是2。因此，中位数在两次操作后增加（3>2）。可以证明这是可能的最小操作数。