C. An Odd Meal
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Eating jellyfish may seem like an odd meal to most of us. But Sally the sea turtle loves eating jellyfish for lunch. Today, her lunch will last for $$$N$$$ minutes. At minute $$$i$$$, Sally eats $$$j_i$$$ jellyfish.

Sally also likes odd numbers. Given the above details of her lunch, she wants you to find out the length of the longest contiguous time interval where the total number of jellyfish she ate during that interval sums to an odd number (if possible).

Input

The first line of input contains $$$N$$$ $$$(1 \leq N \leq 2 \cdot 10^5)$$$. The second line of input contains $$$N$$$ space separated integers denoting $$$j_i$$$ $$$(0 \leq j_i \leq 10^9)$$$.

Output

Please output 1 integer, the length of the longest contiguous time interval where the total number of jellyfish eaten during that interval sums to an odd number.

If it is impossible to find such an interval, output -1.

Examples
Input
7
4 6 8 3 2 12 5
Output
6
Input
2
0 1
Output
2
Input
4
100 200 300 400
Output
-1