You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Time Limit: 2.0 s

Memory Limit: 256.0 MB

Description

Mujammal is a flamboyant boy. He Loves even numbers. His friend Roy is preparing a problem related to even numbers.

You are given array with \(N\) positive integers. You have to divide this array into maximum contigious subarray such that sum of all the elements of each subarray is even.

for example, we can divide the array A[]={4,7,2,5,2} by maximum 3 contigious subarray {4},{7,2,5},{2}.So the answer for this array is 3.

Input

First line of the input takes an integer \(N\) : size of the array
next line takes \(N\) integers : elements of the array

1 <= \(N\) <= \(3*10^5\)
1 <= \(Ai\) <= \(10^7\)

Output

Print one integer : maximum number of subarray
If it's impossible to make each subarray sum even, print -1

Sample

4
4 1 1 2

3