题目描述

阳光社区计划举办一场“创意手工艺品展览会”，社区活动中心有三位热心志愿者担任手工艺指导老师。

展览会预计会有 $n$ 位居民前来学习制作手工艺品。每位居民都有自己感兴趣的手工艺品种类，为了简化问题，我们用 $a_i$ 表示第 $i$ 位居民想学习的手工艺品种类编号。

每位志愿者老师可以提前选择一种自己最擅长的手工艺品种类，用 $1$ 到 $10^9$ 之间的整数 $x$ 来表示，不同的老师可以选择不同的种类。在展览会准备期间，老师们将深入钻研所选种类的制作技巧，达到精通水平。对于选择了种类 $x$ 的老师来说，指导居民制作种类为 $y$ 的手工艺品需要 $|x-y|$ 的准备时间，因为种类越接近他精通的，老师就能越快速地提供指导。

展览会当天，当居民来到活动中心请求学习某种手工艺品时，志愿者老师可以灵活分配由谁来指导。同时，老师们都非常有经验，可以同时指导多位居民。

由于居民们希望尽快开始学习，老师们希望选择合适的专长种类，使得所有居民的最大等待时间尽可能短。请你帮助计算这个最小化的最大等待时间。

输入格式

第一行包含一个整数 $n$ 表示前来学习的居民人数。

第二行包含 $n$ 个整数 $a_{1\sim n}$ 表示居民想学习的手工艺品种类编号。

输出格式

一行一个整数表示答案。

输入样例1

6
1 7 7 9 9 9

输出样例1

0

解释： 三位老师提前选择种类 $1,7,9$，这样每位居民都能立即得到指导。

输入样例2

6
5 4 2 1 30 60

输出样例2

2

解释： 三位老师提前选择种类 $3,30,60$，最大等待时间为 $2$。

输入样例3

9
14 19 37 59 1 4 4 98 73

输出样例3

13

解释： 三位老师提前选择种类 $14,50,85$，最大等待时间为 $13$。

数据规模与约定

对于 $30\%$ 的数据，$1\leq n\leq 10$，$1\leq a_i\leq 100$。

对于 $50\%$ 的数据，$1\leq n\leq 2000$，$1\leq a_i\leq 100$。

对于 $70\%$ 的数据，$1\leq n\leq 2000$。

对于 $100\%$ 的数据，$1\leq n\leq 2\times 10^5$，$1\leq a_i\leq 10^9$。