该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在一条直线道路上有多个住户，现在想在这条直线道路上开一家超市，超市可以开在任何位置，包括住户所在的位置。现在请你编程求解，超市开在哪里，可以使所有住户到商店的距离的总和是最小的。

输入格式

第一行一个整数 $n$，表示有 $n$ 个住户。

第二行有 $n$ 个正整数，表示住户所在位置。

输出格式

输出有一个整数，表示所有住户到超市距离总和的最小值。

4
6 2 9 1

12

5
0 1 2 3 4

6

提示

对于 $60\%$ 的数据 $1\le n\le 1000$。

对于 $100\%$ 的数据 $1\le n\le 10^5$。

$1\le a_i\le 40000$