A. zerorush
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Zerorush is an exciting single-player game played with a sequence of numbers.

The game begins with a sequence of $$$N$$$ integers $$$a_1, a_2, \ldots, a_N$$$. In each turn, the player chooses any number in the sequence and either increases or decreases it by exactly 2. The game ends successfully when at least one number in the sequence reaches zero.

Your task is to determine the minimum number of moves needed to complete the game.

Input

The first line contains one integer $$$N$$$ ($$$1 \leq N \leq 10^6$$$) - the length of the sequence.

The second line contains $$$N$$$ space separated integers $$$a_1, a_2, \ldots, a_N$$$ ($$$-10^9 \leq a_i \leq 10^9$$$) - the sequence.

Output

One line, the minimum number of moves needed to complete the game, or -1 if it is impossible to do so.

Examples
Input
6
6 5 4 3 4 7
Output
2
Input
5
3 11 7 13 9
Output
-1