4297: 木雕玩具（toy）
内存限制：512 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
# 木雕玩具（toy）
### 题目描述
在一个小镇上，有一个专门从事木雕工艺的工作室。由于小镇规模不大，只有**三位**雕刻师在那里工作。
小镇上计划举办一个木制玩具节。工作室的员工们想要为此做好准备。
将会有 $n$ 个人来到工作室请求制作木制玩具。每个人都是独一无二的，他们可能想要不同的玩具。为了简化问题，让我们用 $a_i$ 表示第 $i$ 个人想要的玩具图案。
每位雕刻师都可以**事先**选择一个图案，用一个 $1$ 到 $10^9$ 之间的整数 $x$ 来表示，不同的雕刻师可以选择不同的图案。在节日准备期间，雕刻师将完全掌握制作所选图案玩具的技巧，这将使他们能够立刻切割出木制玩具。对于选择了图案 $x$ 的雕刻师来说，制作图案为 $y$ 的玩具将需要 $|x-y|$ 的时间，因为玩具图案越接近他能立即制作的，雕刻师就越能快速完成工作。
在节日当天，当一个人来到工作室请求制作木制玩具时，雕刻师可以选择谁来接手这份工作。同时，雕刻师们都是非常熟练的人，可以同时为不同的人工作。
由于人们不喜欢等待，雕刻师们希望选择准备的图案，使得所有人的最大等待时间尽可能小，请你求出这个值。
输入
### 输入格式
第一行包含一个整数 $n$ 表示来到工作室的人数。
第二行包含 $n$ 个整数 $a_{1\sim n}$ 表示玩具的图案。
输出
### 输出格式
一行一个整数表示答案。
样例输入 复制
6
1 7 7 9 9 9样例输出 复制
0提示
### 样例 1 输入
```
6
1 7 7 9 9 9
```
### 样例 1 输出
```
0
```
### 样例 1 解释
三位雕刻师事先选择图案 $1,7,9$。
### 样例 2 输入
```
6
5 4 2 1 30 60
```
### 样例 2 输出
```
2
```
### 样例 2 解释
三位雕刻师事先选择图案 $3,30,60$。
### 样例 3 输入
```
9
14 19 37 59 1 4 4 98 73
```
### 样例 3 输出
```
13
```
### 样例 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$。