题目描述

给你一个由 $n$ 个整数组成的数组 $a$ 。

数组 $a_1, a_2, \ldots, a_k$ 的中位数是 $a_{\lceil \frac{k}{2} \rceil}$ ，其中 $a$ 是 按从小到大的顺序 排序过的 。

其中 $\lceil \frac{k}{2} \rceil$ 的含义是 $k$ 除以 $2$ 向上取整，例如 $\lceil \frac{5}{2} \rceil=3$，$\lceil \frac{4}{2} \rceil=2$。

例如，数组 $[9, 5, 1, 2, 6]$ 的中位数是 $5$ ，$a$ 数组排序后是 $[1, 2, 5, 6, 9]$ 中，下标 $\lceil \frac{5}{2} \rceil = 3$ 处的数字是 $5$ 。

而数组 $[9, 2, 8, 3]$ 的中位数是 $3$ ，$a$ 数组排序后是 $[2, 3, 8, 9]$ 中，下标 $\lceil \frac{4}{2} \rceil = 2$ 处的数字是 $3$ 。

您可以选择一个整数 $i$ ( $1 \le i \le n$ )，并在一次运算中将 $a_i$ 增加 $1$ 。意思是你可以选择让这个数组中的任何一个位置的元素增加 $1$。

你的任务是找出改变数组中位数所需的最少操作次数。具体可以结合样例的解释

注意数组 $a$ 不一定包含不同的数。

输入格式

第一行包含一个整数 $n$ - 数组的长度 $a$ 。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$ - 数组 $a$ 。

输出格式

输出一个整数 - 增加数组中位数所需的最少操作数。

3
2 2 8

1

5
5 5 5 4 5

3

样例解释

在第一个测试案例中，对第一个数字进行一次运算，得到数组 $[3, 2, 8]$ ，然后我们将这个数组从小到大排序后可以得到 $[2, 3, 8]$，这个数组的中位数是 $3$ ，原数组 $[2, 2, 8]$ 的中位数是 $2$ ，因此，只需一次操作，中位数就增加了（ $3>2$ ）。

在第二个测试用例中，可以对位于索引 $1, 2, 3$ 的每个数字进行一次操作，得到数组 $[6, 6, 6, 4, 5]$ ，这个数组的中位数是 $6$ 。原数组 $[5, 5, 5, 4, 5]$ 的中位数是 $5$ ，因此，中位数在三次运算中增加了（ $6 > 5$ ）。可以证明，这是最少操作次数。

数据规模与约定

对于 $50\%$ 的数据，满足 $1\leq n,a_i\leq 1000$

对于 $100\%$ 的数据，满足 $1\leq n\leq 10^5,1\leq a_i\leq 10^9$