問題文

二次元平面の原点 $(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$ 回行動した後、原点に戻ることはできません。