题目描述

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

数组 $q_1,q_2,…,q_k$ 的中位数是 $p⌈\frac {k}{2}⌉$ ，其中 $p$ 是按非递减顺序排列的数组 $q$ 。 例如，数组 $[9,5,1,2,6]$ 的中位数是 $5$ ，在排序数组$[1,2,5,6,9]$ 中，索引 $⌈\frac {5}{2}⌉=3$ 处的数字是 $5$ ；数组 $[9,2,8,3]$ 的中位数是 $3$ ，在排序数组 $[2,3,8,9]$ 中，索引 $⌈\frac {4}{2}⌉=2$ 处的数字是 $3$ 。

您可以选择一个整数 $i( 1≤i≤n)$，并在一次操作中将 $a_i$ 增加 $1$ 。

你的任务是找出增加数组中位数所需的最少运算次数。

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

输入格式

第一行包含一个整数 $n(1 \leq n \leq 10^5)$ - 数组 $a$ 的长度。 第二行包含 $n$ 个整数 $a_1,a_2,...,a_n(1 \leq a_i \leq 10^9)$ -数组 $a$ 。

输出格式

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

样例

样例输入 #1

3
2 2 8

样例输出 #1

1

样例输入 #2

4
7 3 3 1

样例输出 #2

2

提示

样例解释 $1$: 对第一个数字进行一次运算，得到数组 $[3,2,8]$，这个数组的中位数是 $3$，因为它是非递减排序数组 $[2,3,8]$ 中索引 $⌈\frac {3}{2}⌉=2$ 处的数字。原数组 $[2,2,8]$ 的中位数是 $2$，因为它是非递减排序数组 $[2,2,8]$ 中索引 $⌈\frac {3}{2}⌉=2$ 处的数字。因此，只需一次操作，中位数就增加了。$(3>2)$