在一个小镇上，有一个专门从事木雕工艺的工作室。由于小镇规模不大，只有三位雕刻师在那里工作。

小镇上计划举办一个木制玩具节。工作室的员工们想要为此做好准备。

将会有 n 个人来到工作室请求制作木制玩具。每个人都是独一无二的，他们可能想要不同的玩具。为了简化问题，让我们用 a_i 表示第 i 个人想要的玩具图案。

每位雕刻师都可以事先选择一个图案，用一个 1 到 10^9 之间的整数 x 来表示，不同的雕刻师可以选择不同的图案。在节日准备期间，雕刻师将完全掌握制作所选图案玩具的技巧，这将使他们能够立刻切割出木制玩具。对于选择了图案 x 的雕刻师来说，制作图案为 y 的玩具将需要 |x-y| 的时间，因为玩具图案越接近他能立即制作的，雕刻师就越能快速完成工作。

在节日当天，当一个人来到工作室请求制作木制玩具时，雕刻师可以选择谁来接手这份工作。同时，雕刻师们都是非常熟练的人，可以同时为不同的人工作。

由于人们不喜欢等待，雕刻师们希望选择准备的图案，使得所有人的最大等待时间尽可能小，请你求出这个值。

第一行包含一个整数 n 表示来到工作室的人数。

第二行包含 n 个整数 a_{1\sim n} 表示玩具的图案。

一行一个整数表示答案。

样例 1 解释

三位雕刻师事先选择图案 1,7,9。

样例 2 解释

三位雕刻师事先选择图案 3,30,60。

样例 3 解释

三位雕刻师事先选择图案 14,50,85。

数据规模与约定

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