Problem Statement

You are given a sequence of $n$ integers $a_1, a_2, \dots, a_n$. You need to perform a series of operations to transform this sequence.

An operation consists of choosing an index $i$ ($1 \le i < n$) and replacing the pair $(a_i, a_{i+1})$ with their sum $(a_i + a_{i+1})$. This reduces the length of the sequence by 1. You must continue this process until the sequence consists of a single element.

Your goal is to maximize the number of elements in the sequence that are even throughout the entire process.

Input

The first line contains a single integer $n$ ($1 \le n \le 10^5$).

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$).

Output

Output a single integer representing the maximum number of even elements that can be obtained.

Examples

Input 1

3
1 2 3

Output 1

1

Note

In the first example, if we add 1 and 2, we get 3, 3. Neither is even. If we add 2 and 3, we get 1, 5. Neither is even. However, if we perform the operations optimally, we can obtain one even number.