{"raw_statement":[{"iden":"problem statement","content":"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.\nTakahashi will perform the following actions $N$ times on the plane.\n\n*   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$.\n\nAfter performing $N$ actions, Takahashi must return to the origin $(0,0)$.\nDetermine 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)."},{"iden":"constraints","content":"*   $1 \\leq N \\leq 2 \\times 10^5$\n*   $2 \\leq D_i \\leq 2 \\times 10^5$\n*   $D_i\\ (1\\leq i \\leq N)$ is even.\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$N$\n$D_1$ $D_2$ $\\dots$ $D_N$"},{"iden":"sample input 1","content":"3\n2 4 6"},{"iden":"sample output 1","content":"4\n\nIf 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."},{"iden":"sample input 2","content":"5\n2 2 2 2 6"},{"iden":"sample output 2","content":"3\n\nIf 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.\nTakahashi can also move to non-grid points."},{"iden":"sample input 3","content":"2\n2 200000"},{"iden":"sample output 3","content":"\\-1\n\nTakahashi cannot return to the origin after performing $N$ actions as described above."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}