← 返回题目列表

AtCoder · agc062_d

D. 在附近散步

中文机器翻译题面 查看原题

分数: 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 如上所述的操作。