A71478. 最小距离(average.cpp)

Cotton最近遇到了一个举世难题，他要为 YYT 的公司的员工规划居住区的位置。

YYT家里有矿，每天他公司的员工要去上矿。矿分布在一条线段上，总共有 n 个矿，第 i 个矿的距离线段左端点的距离为 a[i] 米。

YYT作为良心企业家，为了减轻公司员工的负担，他希望居住区到每个矿的距离和最小。然而弱小的Cotton并不会这个问题，现在你能帮帮他吗？

第一行一个整数 n ，表示矿的数量。

第二行 n 个整数，第 i 个数 a[i] 表示第 i 个矿距离线段左端点的距离。

一个整数，表示居住区距离线段左端点的距离，单位为米。如果有多个答案请输出最小的。

【数据范围】

对于 20\% 的数据，n≤100,1≤a[i]≤100 。

对于 50\% 的数据，n≤1000000,1≤a[i]≤100 。

对于 80\% 的数据，n≤1000000,1≤a[i]≤1000000。

对于 100\% 的数据，n≤1000000,1≤a[i]≤1000000000。