街道的中心

题目描述

城市商业街主干道是一条笔直的道路，商业街里有 n 家店铺，现给定 n 个店铺的位置，请在这条道路上找到一个中心点，使得所有店铺到这个中心点的距离之和最小，并输出这个最小值。

输入格式

第一行：单个正整数 n。

第二行：n 个整数表示一个店铺的位置。

输出格式

单个整数：表示商铺到中心点距离之和的最小值。

输入样例

4  

-2  0  2  0  

输出样例

4

说明提示

数据范围：

· -5000≤x_i≤5000

· 对于 30% 的数据，1≤n≤20

· 对于 60% 的数据，1≤n≤2000

· 对于 100% 的数据，1≤n≤100000

样例解释：

最优中心设置在坐标 0 处，总距离为：

∣-2-0∣+∣0-0∣+∣2-0∣+∣0-0∣=2+0+2+0=4

限制

时间限制：1000ms

内存限制：512MiB