/ 
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 1100 点
問題文
二次元平面の原点 (0,0) にメモ帳を持った高橋君がいます。メモ帳には N 個の偶数 D_i\ (1\leq i \leq N) が書かれています。
これから高橋君は二次元平面上で以下の行動を N 回行います。
- メモ帳に書かれている偶数を 1 つ選んで消す。選んだ偶数を 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|) の最小値を求めてください（この値は整数になることが証明できます）。
制約
- 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
高橋君が 1 回目から 3 回目の行動でそれぞれ 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
高橋君が 1 回目から 5 回目の行動でそれぞれ 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
2 2 200000
出力例 3
-1
高橋君は上記のように N 回行動した後、原点に戻ることはできません。
Score : 1100 points
Problem Statement
Takahashi, with a notepad, is standing at the origin (0,0) of a two-dimensional plane. His notepad has N even numbers D_i\ (1\leq i \leq N) written.
Takahashi will perform the following actions N times on the plane.
- He chooses and erases one even number written on the notepad. Let d be the chosen even number. He then moves to a point exactly d distance away in terms of Manhattan distance. More precisely, if Takahashi is currently at the coordinates (x,y), he moves to a point (x',y') such that |x-x'|+|y-y'|=d.
After performing N actions, Takahashi must return to the origin (0,0).
Determine if it is possible to perform N actions in such a way. If it is possible, find the minimum value of \displaystyle \max_{1\leq i \leq N}(|x_i|+|y_i|), where (x_i,y_i) are the coordinates where Takahashi is located after the i-th action (we can prove that this value is an integer).
Constraints
- 1 \leq N \leq 2 \times 10^5
- 2 \leq D_i \leq 2 \times 10^5
- D_i\ (1\leq i \leq N) is even.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N D_1 D_2 \dots D_N
Output
If it is impossible to perform N actions as described above, print -1. If it is possible, print the minimum value of \displaystyle \max_{1\leq i \leq N}(|x_i|+|y_i|) as an integer.
Sample Input 1
3 2 4 6
Sample Output 1
4
If Takahashi erases 2,6,4 from his notepad for the first to third actions, respectively, and moves as (0,0)\rightarrow (0,2) \rightarrow (-4,0) \rightarrow (0,0), then \displaystyle \max_{1\leq i \leq N}(|x_i|+|y_i|) is 4, which is the minimum.
Sample Input 2
5 2 2 2 2 6
Sample Output 2
3
If Takahashi erases 2,2,6,2,2 from his notepad for the first to fifth actions, respectively, and moves as (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), then \displaystyle \max_{1\leq i \leq N}(|x_i|+|y_i|) is 3, which is the minimum.
Takahashi can also move to non-grid points.
Sample Input 3
2 2 200000
Sample Output 3
-1
Takahashi cannot return to the origin after performing N actions as described above.