解题思路

给定 $n$ 个整数 $a_1,\dots,a_n$，希望选一个整数 $x$ 使

最小；若最优解不唯一，取最小的 $x$。

题目内容

小O生产了 $n$ 种不同的物质，编号为 $1$ ~ $n$。第 $i$ 种物质的活跃值为 $a_i$ 。直接将这些物质融合非常不稳定，因此小O决定额外制作一个稳定剂。

若稳定剂的整数值为 $x$ ，则融合所有物质后产生的不稳定值为 $\sum^n_{i=1}∣x-a_i∣$。小O希望找到一个整数 $x$ ，使得不稳定值最小；若存在多个最优的 $x$ ，则选择其中最小的一个。

输入描述

第一行输入一个整数 $n(1 ≦ n≦2×10^5)$，表示不同物质的数量；

第二行输入 $n$ 个整数 $a_1,a_2,...,a_n(1≦ a_i ≦ 10^9)$，表示每种物质的活跃值。

输出描述

输出一个整数，表示你选择的稳定剂数值 $x$ 。

样例1

输入

3
1 5 9

输出

5

说明

对于此样例选择 $5$ 不稳定值为 $|5-1|+|5-5|+|5-9|=8$ ，可以证明此时最小。

样例2

输入

4
1 10 2 9

输出

2