题目描述

谢思怡，下班我们去钓鱼吧！这次我请！

虾仁的好盆友思怡有很多书，共摆了 $n$ 堆，每堆书籍有 $a_i$ 个。

虾仁可以通过增加或者降低某些堆的高度来保持他们高度一致。设降低的总高度为 $d_1$ 增加的总高度为 $d_2$ ，现在思怡想要让这些书变得相同高，同时 $d_1+d_2$ 最小，如果有多个同时满足 $d_1+d_2$ 最小的高度 $h$，那么选择高度 $h$ 最小的一个。虾仁决定帮他整理这些书籍，让这些书变得一样高的同时 $d_1+d_2$ 最小，请问虾仁选择的高度是多少呢？

输入格式

第一行一个整数 $n\ \left(1 \le n \le 2 \times 10^5\right)$ 表示总堆数。

第二行 $n$ 个整数 $a_i\ \left(1 \le a_i \le 2 \times 10^5\right)$ 表示第 $i$ 堆的高度。

输出格式

输出一个整数表示答案。

样例输入

5
2 4 1 7 3

样例输出

3

样例解释

虾仁选择高度为 $3$，那么降低的总高度为：$d_1=0+1+0+4+0=5$，增加的总高度为：$d_2=1+0+2+0+0=3$，可以证明虾仁选择的高度使得 $d_1+d_2=8$ 这个值最小。