当前没有测试数据。

题目描述

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$ 。

来源

2021-2022年中山市东区第一届义务教育段学生信息学邀请赛 T3