Unstable Sequence

$N$ natural numbers are lined up from left to right. The $i$-th number from the left ($1 \le i \le N$) is $A_i$.

You may pick any number of these numbers. You cannot pick none, so you must pick at least one.

Let $k$ be the number of picked numbers, and let the picked numbers be $B_1, B_2, \cdots, B_k$ in order. They keep the order they had in the original row.

For example, take $N = 5$ and $A = [3, 1, 4, 1, 5]$. If you pick the 2nd, 4th, and 5th numbers from the left, then $k = 3$ and $B = [1, 1, 5]$.

Call $B$ an unstable sequence if the sum of every pair of adjacent numbers is odd: the sum of $B_1$ and $B_2$, the sum of $B_2$ and $B_3$, and so on. If $k = 1$, then $B$ counts as an unstable sequence.

For example, if $k = 6$ and $B = [1, 4, 3, 2, 5, 4]$, then the adjacent sums are 5, 7, 5, 7, and 9. All are odd, so $B$ is an unstable sequence.

Also, if $k = 1$ and $B = [2]$, then $B$ is an unstable sequence because $k = 1$.

But if $k = 4$ and $B = [4, 5, 1, 2]$, the first adjacent sum is 9 (odd), but the sum of 5 and 1 is 6 (even). Some adjacent sums are not odd, so $B$ is not an unstable sequence.

You must pick numbers so that $B$ is an unstable sequence, and you want to pick as many numbers as possible. Write a program that finds the maximum number of numbers you can pick.

For example, take $A = [4, 5, 1, 2]$. Picking all four numbers gives $B = [4, 5, 1, 2]$, which is not an unstable sequence, so four numbers are not possible. Picking the 1st, 3rd, and 4th numbers gives $B = [4, 1, 2]$. The sums 4 + 1 = 5 and 1 + 2 = 3 are both odd, so $B$ is an unstable sequence. Three is the maximum.

The first line contains $N$.

The second line contains $A_1, A_2, \cdots, A_N$ in order, separated by spaces.

Print the answer on the first line.

• Every given number is a natural number.
• $1 \le N \le 300\,000$
• $1 \le A_i \le 100\,000$ ($1 \le i \le N$)