题目描述

高桥君手持一本记事本，站在二维平面上的原点 $(0,0)$。记事本上写有 $N$ 个偶数 $D_i\ (1\leq i \leq N)$。

接下来，高桥君将在二维平面上进行 $N$ 次如下操作：

• 从记事本上选择并划去一个偶数。设选中的偶数为 $d$，则他会移动到与当前位置曼哈顿距离恰好为 $d$ 的某个点。更准确地说，若当前坐标为 $(x, y)$，则他会移动到满足 $|x-x'|+|y-y'|=d$ 的某个点 $(x', y')$。

高桥君必须在 $N$ 次操作后回到原点 $(0,0)$。

请判断是否存在一种操作顺序和移动方式，使得高桥君能够完成上述 $N$ 次操作并回到原点。如果存在，请求出所有可能方案中，$i$ 次操作后高桥君所在坐标为 $(x_i, y_i)$ 时，$\displaystyle\max_{1\leq i\leq N}(|x_i|+|y_i|)$ 的最小值（可以证明该值为整数）。

输入格式

输入从标准输入读入，格式如下：

$N$ $D_1$ $D_2$ $\dots$ $D_N$

输出格式

如果无法完成 $N$ 次操作并回到原点，输出 -1。

如果可以，请输出 $\displaystyle\max_{1\leq i\leq N}(|x_i|+|y_i|)$ 的最小值（输出一个整数）。

样例 1

输入

3
2 4 6

输出

4

样例 2

输入

5
2 2 2 2 6

输出

3

样例 3

输入

2
2 200000

输出

-1

说明/提示

限制条件

• $1\leq N\leq 2\times 10^5$
• $2\leq D_i\leq 2\times 10^5$
• $D_i$（$1\leq i\leq N$）均为偶数
• 所有输入均为整数

样例解释 1

高桥君依次选择 $2,6,4$ 并划去，移动路径为 $(0,0)\rightarrow (0,2)\rightarrow (-4,0)\rightarrow (0,0)$，此时 $\displaystyle\max_{1\leq i\leq N}(|x_i|+|y_i|)$ 为 $4$，且这是最小值。

样例解释 2

高桥君依次选择 $2,2,6,2,2$ 并划去，移动路径为 $(0,0)\rightarrow (\frac{1}{2},\frac{3}{2})\rightarrow (0,3)\rightarrow (0,-3)\rightarrow (-\frac{1}{2},-\frac{3}{2})\rightarrow (0,0)$，此时 $\displaystyle\max_{1\leq i\leq N}(|x_i|+|y_i|)$ 为 $3$，且这是最小值。高桥君可以移动到非格点的位置。

样例解释 3

高桥君无法在 $N$ 次操作后回到原点。

由 ChatGPT 4.1 翻译