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.