题目描述

Takahashi 拿着一个记事本站在二维平面的原点$(0,0)$上。他的记事本上写着 $N$ 个偶数 $D_i \ (1\leq i \leq N)$。

Takahashi 将在平面上执行以下操作 $N$ 次。

• 他选择并擦除记事本上的一个偶数。设选中的偶数为 $d$。然后他按曼哈顿距离移动到距离他当前位置 $d$ 远的点。更具体地说，如果 Takahashi 当前位于坐标 $(x,y)$，他将移动到一个点 $(x',y')$，使得 $|x-x'|+|y-y'|=d$。

执行完 $N$ 次操作后，Takahashi 必须回到原点 $(0,0)$。

确定是否可能以这种方式执行 $N$ 次操作。如果可能，找到$\\displaystyle \\max_{1\leq i \leq N}(|x_i|+|y_i|)$ 的最小值，其中 $(x_i,y_i)$ 是第 $i$ 次操作后 Takahashi 所在的坐标（我们可以证明该值是整数）。

约束条件

• $1 \leq N \leq 2 \times 10^5$
• $2 \leq D_i \leq 2 \times 10^5$
• $D_i\ (1\leq i \leq N)$ 是偶数。
• 输入中的所有数字都是整数。

输入

输入遵循以下格式，从标准输入给出：

$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

示例输出 1

4

如果 Takahashi 按顺序擦除记事本上的 $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

5
2 2 2 2 6

示例输出 2

3

如果 Takahashi 按顺序擦除记事本上的 $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$，这是最小值。

Takahashi 也可以移动到非网格点。

示例输入 3

2
2 200000

示例输出 3

-1

Takahashi 无法按照上述描述执行 $N$ 次操作后返回原点。