You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

集会广场

题目描述

在云南的崇山峻岭之间，散落着 $n$ 个美丽的村落。这些村落恰好分布在一条笔直的山谷中，我们可以将它们的位置看作数轴上的点，第 $i$ 个村落的坐标为 $a_i$。

为了方便村民们赶集交流，村长决定选择一个位置 $x$ 修建一个集会广场。村民们希望广场到所有村落的距离之和尽可能小，这样大家都能少走山路。距离之和定义为：

作为村长的智囊，请你计算出这个最小可能的总距离。

输入格式

第一行包含一个整数 $n$，表示村落的数量。 第二行包含 $n$ 个整数 $a_1,a_2,\dots,a_n$，表示各个村落在数轴上的坐标。

输出格式

输出一个整数，表示广场到所有村落的最小总距离。

样例输入

5
1 2 3 4 5

样例输出

6

数据范围

$1 \le n \le 10^5$, $-10^9 \le a_i \le 10^9$