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.