普及-⏱ 1000ms💾 256MB#P3079

题目描述

快递公司要在数轴上选一个位置设集合点,使所有驿站到集合点的距离之和最小。给定 $n$ 个驿站的坐标,输出最小化的总距离。(最优位置是中位数所在处。)

输入格式

第一行整数 $n$;第二行 $n$ 个整数坐标。

输出格式

一行一个整数,即最小总距离。

数据范围

$$1 \le n \le 10^5,\ 0 \le 坐标 \le 10^9$$

样例输入 #1
1
42
样例输出 #1
0
样例输入 #2
2
0 10
样例输出 #2
10