题目描述

王老师有一个长度为 $n$ 的序列 $a$。

小姜定义一个序列 a 的权值为 $mex${$a_1​ +a_2 ,a_2 +a_3,...,a_n−1 +a_n$ }，其中 $mex${$S$} 表示集合 $S$ 中最小的未出现的非负整数。

王老师现在可以将序列 a 任意排列，他想让序列 a 的权值尽可能小，你能告诉他该最小权值吗？

输入格式

输入的第一行包含一个整数 n。

接下来一行包含 n 个整数，第 i 个整数表示 $a_i$ 。

输出格式

输出共一行，包含一个整数，表示最小权值。

样例输入 1

3
0 0 1

样例输出 1

0

样例输入 2

5
0 1 2 3 2

样例输出 2

0

样例输入 3

见下发大样例 arrange3.in 样例输出 3

见下发大样例 arrange3.out 样例输入 4

见下发大样例 arrange4.in 样例输出 4

见下发大样例 arrange4.out 提示/说明

样例1解释 将序列 a 重排为 $a_1 =0,a_2 =1,a_3 =0$，可以得到最小权值 0。

数据范围 对于 40% 的数据，保证 n≤10。

对于另外 20% 的数据，保证序列 a 中 0 的个数不超过 $⌊ (2n+1)/2 ⌋$。

对于 100% 的数据，$2≤n≤10^6 ，0≤a_i​ ≤10^9$ 。