在一条数轴上有 $N$ 家商店，它们的坐标分别为 $A_1 \sim A_N$。

现在需要在数轴上建立一家货仓，每天清晨，从货仓到每家商店都要运送一车商品。

为了提高效率，求把货仓建在何处，可以使得货仓到每家商店的距离之和最小。

输入格式

第一行输入整数 $N$。

第二行 $N$ 个整数 $A_1 \sim A_N$。

输出格式

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

数据范围

$1 \le N \le 100000$,
$0 \le A_i \le 40000$

输入样例：

4
6 2 9 1

输出样例：

12

下面按 k=1..25 说明这套“货仓选址使距离和最小（应取中位数）”数据分别在卡哪些常见错误做法。 （正确：选任一 中位数 位置可使 (\sum |A_i-x|) 最小；答案要用 64 位累加。）

1. 样例：基础正确性（乱序输入，需先排序/找中位数）。
2. n=1：答案 0；卡边界处理/输出错误。
3. 全相同：答案 0；卡多余计算、或用均值/中位数都应对但可检验实现。
4. 两端极值 [0,40000]（n=2）：多解（任意 x∈[0,40000] 都最优），距离和固定 40000；卡错误地强行取整数平均后算错（不应影响但可检验公式）。
5. 偶数 n 且最优区间较大 [1,2,10,11]：最优 x 在 [2,10]；卡“偶数时必须取某个点（例如取平均并四舍五入）”但算距离时写错、或取错下标。
6. 奇数 n 且有远端离群 [1,2,10,11,100]：唯一中位数；卡把均值当答案会偏。
7. 已排序小数组 0..19：卡无需依赖输入顺序；也卡中位数下标是否正确。
8. 逆序 19..0：应与 #7 相同；卡没排序/把输入当有序。
9. **大量重复 + 两端对称 `[0]50+[40000]50：偶数且多解；卡中位数边界处理、也卡 64 位累加（距离和很大）。
10. 小随机（30 个）：综合正确性，卡各种小 bug。
11. 大簇 + 少量极端离群：例如 100 个 20000，加几个 0/40000/39999；卡把“离群点”错误拉偏（用均值会错）。
12. 1000 个全 40000：答案 0；卡大 n 的 I/O/循环边界。
13. 0..99 每个重复 10 次（n=1000）：卡重复值、以及中位数位置计算（(n-1)//2 vs n//2）。
14. n=99999 随机压力：卡性能（不能 O(n*值域) 枚举 x）、以及排序/选择算法稳定性。
15. n=100000 随机压力：同 #14，更强。
16. n=100000 全 0：答案 0；强卡性能/边界（不应溢出/不应超时）。
17. n=100000 半 0 半 40000：距离和巨大；强卡 64 位累加（32 位会爆）。
18. 专卡“用平均数代替中位数” [0,0,0,0,40000]：均值=8000，但最优是 0；卡错误思路。
19. 偶数 n 两个中位数之间 [0,0,10,10]：最优区间 [0,10]；卡偶数时取均值后再做整数截断/四舍五入导致实现 bug（尤其有人先取 x 再做奇怪修正）。
20. 靠边界混合 [0,1,1,1,39999,40000,40000]：卡边界 0/40000、以及绝对值累加正确性。
21. n=100000 仅 3 个取值（100/200/300）大量重复：卡计数/桶思路写错（频次处理），也卡性能。
22. n=100000 值域很小 0..100 的随机：卡“值域小但 n 大”的性能/桶实现正确性。
23. 0..40000 全覆盖（n=40001）：中位数=20000，答案可验证；卡下标/奇数中位数取错。
24. 两团远离 + 少量中间点：1000*500 + 39000*500 + 20000*10；卡“取均值/取众数/取中间点”类错误。
25. n=5000 随机（用来卡枚举 x=0..40000 的慢做法）：如果有人对每个候选点算距离（O(n*40000)）会明显慢；也卡排序/选择正确性。

如果你还想更精准地卡某个特定错误（比如：偶数时取错中位数下标、或把距离和写成平方和），把那种错误写法描述一下，我可以再补几组一针见血的反例。