货仓选址

题目描述

在一条数轴上有 $n$ 个货仓，第 $i$ 个货仓的坐标是 $x_i$。现在要在数轴上选一个整数坐标 $p$ 建一座配送中心，使得配送中心到所有货仓的距离之和最小，也就是让 $\sum_{i=1}^{n}|x_i - p|$ 最小。

请输出这个最小的距离之和。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $x_1, x_2, \dots, x_n$。

输出格式

一行一个整数，表示最小的距离之和。

样例

输入样例

4
6 2 9 1

输出样例

12

样例解释

把配送中心建在坐标 $6$（或 $2$）处，距离之和为 $5 + 4 + 0 + 3 = 12$，这是最小的。

数据范围

$1 \le n \le 2 \times 10^5$，$-10^9 \le x_i \le 10^9$；坐标可以为负数，同一坐标上可能有多个货仓。