题目描述

在一条公路上有$N$个零食,它们的坐标分别为 $A_{1},A_{2}...A_{N}$
何小猪要吃到所有的零食,她要选择一个起始位置,使得她到所有的零食的距离之和最小
如果起始位置为$x$,何小猪希望最小化

$Tip$:如果需要将数组从小到大排序可以借鉴如下代码

for(int i=0;i<N;i++){
    for(int j=i+1;j<N;j++){//枚举后面比我小的
        if(A[j]<A[i]){
            int t=A[j];//交换位置
            A[j]=A[i];
            A[i]=t;
        }
    }
}
//这段代码实现将数组A中,下标0~n的元素从小到大排列

输入格式

第一行一个整数$N$---代表零食的个数$(1 \le N \le 10^{3})$
第二行$N$个整数$A_{1},A_{2}...A_{N}$,代表每一个零食的位置$(1 \le A_{i} \le 10^{9})$

输出格式

输出一行代表到所有零食的距离和的最小值

样例

4
6 2 9 1

12