分数: 1100 点
问题陈述
高桥拿着记事本站在原点 二维平面的 (0,0) 。他的记事本上有 N 偶数 D_i\ (1\leq i \leq N) 写的。
高桥将执行以下操作 飞机上 N 次。
- 他选择并删除记事本上写的一个偶数。让 d 是所选的偶数。然后他准确地移动到一个点 d 以曼哈顿距离表示的距离。更准确地说,如果高桥当前位于坐标处 (x,y),他移动到一个点 (x',y') 这样 |x-x'|+|y-y'|=d.
执行后 N 行动,高桥必须返回原点 (0,0).
确定是否可以执行 N 以这样的方式行动。如果可以的话,求最小值 \displaystyle \max_{1\leq i \leq N}(|x_i|+|y_i|),其中 (x_i,y_i) 是高桥所在的坐标 i-第一个动作(我们可以证明这个值是一个整数)。
约束
- 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
如果高桥擦除 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|) is 4,这是最小值。
示例输入 2
5 2 2 2 2 6
示例输出 2
3
如果高桥擦除 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|) is 3,这是最小值。
高桥也可以移动到非网格点。
示例输入 3
2 2 200000
示例输出 3
-1
高桥表演后无法返回原点 N 如上所述的操作。