说明

在一条数轴上有 $N$ 家商店， 它们的坐标分别为$A_{1}$ ∼ $A_{N}$。 现在需要在数轴上建立一家货仓， 每天清晨， 从货仓到每家商店都要运送一车商品。 为了提高效率， 求把货仓建在何处， 可以使得货仓到每家商店的距离之和最小。

输入格式

第一行输入整数$N$

第二行 $N$个整数 $A_{1}$ ∼ $A_{N}$

输出格式

输出一个整数， 表示距离之和的最小值

样例

4
6 2 9 1

12

数据范围

$1\leqslant N \leqslant 10^{5},0\leqslant A_{i}\leqslant 4\times 10^{4}$

来源

• 算法竞赛进阶指南