题目描述

在一条直线上，有 $n$ 个人，其中第 $i$ 个人在直线上的坐标为 $x_i$。

请在直线上，找到一个聚会点，聚会点可以在直线的任何位置上，使得所有人到达这个聚会点的路程之和达到最小。输出这个最小值。

输入格式

• 单个整数：表示 $n$
• $n$ 个整数：表示 $x_1$ 到 $x_n$

输出格式

数据范围

• $30\%$ 的数据，$1\leq n\leq 100$
• $60\%$ 的数据，$1\leq n\leq 5,000$
• $100\%$ 的数据，$1\leq n\leq 100,000$
• $-20,000\leq x_i\leq 20,000$

样例数据

输入:

5
3 1 4 1 5

输出:

7