木雕玩具 描述
在一个小镇上,有一个专门从事木雕工艺的工作室。由于小镇规模不大,只有三位雕刻师在那里工作。
小镇上计划举办一个木制玩具节。工作室的员工们想要为此做好准备。
将会有 n 个人来到工作室请求制作木制玩具。每个人都是独一无二的,他们可能想要不同的玩具。为了简化问题,让我们用 a i a i 表示第 i 个人想要的玩具图案。
每位雕刻师都可以事先选择一个图案,用一个 1 到 1 0 9 10 9 之间的整数 x 来表示,不同的雕刻师可以选择不同的图案。在节日准备期间,雕刻师将完全掌握制作所选图案玩具的技巧,这将使他们能够立刻切割出木制玩具。对于选择了图案 x 的雕刻师来说,制作图案为 y 的玩具将需要 ∣ x − y ∣ ∣x−y∣ 的时间,因为玩具图案越接近他能立即制作的,雕刻师就越能快速完成工作。
在节日当天,当一个人来到工作室请求制作木制玩具时,雕刻师可以选择谁来接手这份工作。同时,雕刻师们都是非常熟练的人,可以同时为不同的人工作。
由于人们不喜欢等待,雕刻师们希望选择准备的图案,使得所有人的最大等待时间尽可能小,请你求出这个值。
输入 第一行包含一个整数 n 表示来到工作室的人数。
第二行包含 n 个整数 a 1 ∼ n a 1∼n 表示玩具的图案。
输出 一行一个整数表示答案。
输入样例 1
6 1 7 7 9 9 9 输出样例 1
0 输入样例 2
6 5 4 2 1 30 60 输出样例 2
2 输入样例 3
9 14 19 37 59 1 4 4 98 73 输出样例 3
13 提示
对 于 30 % 的 数 据 , 1 ≤ n ≤ 10 , 1 ≤ a i ≤ 100 。 对于30%的数据,1≤n≤10,1≤a i ≤100。 对 于 50 % 的 数 据 , 1 ≤ n ≤ 2000 , 1 ≤ a i ≤ 100 。 对于50%的数据,1≤n≤2000,1≤a i ≤100。 对 于 70 % 的 数 据 , 1 ≤ n ≤ 2000 。 对于70%的数据,1≤n≤2000。 对 于 100 % 的 数 据 , 1 ≤ n ≤ 2 × 1 0 5 , 1 ≤ a i ≤ 1 0 9 。 对于100%的数据,1≤n≤2×10 5 ,1≤a i ≤10 9 。 样例 1 解释 三位雕刻师事先选择图案 1,7,9。
样例 2 解释 三位雕刻师事先选择图案 3,30,60。
样例 3 解释 三位雕刻师事先选择图案 14,50,85。