小 C 有一个长度为 n 的序列 A。

小 K 定义一个序列 A 的权值为 {mex}\{ A_1+A_2,A_2+A_3,...,A_{n-1}+A_n \}，其中 {mex}{S} 表示集合 S 中最小的未出现的非负整数。

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

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

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

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

样例 1 解释

将序列 A 重排为 A_1=0,A_2=1,A_3=0，可以得到最小权值 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。