4354: T1 序列重排（arrange）
内存限制：512 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：3
解决：1
题目描述
## T1 序列重排（arrange）
### 题目描述
小 C 有一个长度为 $n$ 的序列 $A$。
小 K 定义一个序列 $A$ 的权值为 $\operatorname{mex}\{A_1+A_2,A_2+A_3,...,A_{n-1}+A_n\}$，其中 $\operatorname{mex}\{S\}$ 表示集合 $S$ 中最小的未出现的非负整数。
小 C 现在可以将序列 $A$ 任意排列，他想让序列 $A$ 的权值尽可能小，你能告诉他该最小权值吗？
输入
### 输入格式
输入的第一行包含一个整数 $n$。
接下来一行包含 $n$ 个整数，第 $i$ 个整数表示 $A_i$。
输出
### 输出格式
输出共一行，包含一个整数，表示最小权值。
样例输入 复制
3
0 0 1样例输出 复制
0提示
### 样例 1 输入
```
3
0 0 1
```
### 样例 1 输出
```
0
```
### 样例 1 解释
将序列 $A$ 重排为 $A_1=0,A_2=1,A_3=0$，可以得到最小权值 $0$。
### 样例 2 输入
```
5
0 1 2 3 2
```
### 样例 2 输出
```
0
```
### 其余样例见下发文件。
### 数据规模与约定
- 对于 $40\%$ 的数据，保证 $n\le 10$。
- 对于另外 $20\%$ 的数据，保证序列 $A$ 中 $0$ 的个数不超过 $\lfloor\frac{n+1}{2}\rfloor$。
- 对于 $100\%$ 的数据，$2\le n\le 10^6$，$0\le A_i\le 10^9$。