题目描述

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

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

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

输入格式

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

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

输出格式

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

样例

3
3 4 5

4

数据范围

• 对于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。