Скоро Codeforces Round 1133 (Div. 1, Div. 2)! Регистрация здесь. ×
J. Can you even?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output
42... so pretty.
— GePeTo

In order to obtain more food tokens, you plan to present the GePeTo overlord with an array of numbers $$$A$$$. As they were trained on more even numbers than odd numbers, GePeTo prefers even numbers, so you want to change some numbers in $$$A$$$ to maximize the number of even numbers.

Since you are already the first in line, you only have time to apply a single operation to $$$A$$$: pick a number $$$X$$$ and a range $$$[L,R]$$$ and add $$$X$$$ to elements $$$A_L, \ldots, A_R$$$. After performing this operation exactly once, what is the maximum possible number of even numbers in $$$A$$$?

Input

The first line contains an integer $$$N$$$. ($$$1 \leq N \leq 2 \cdot 10^3$$$)

The second line contains $$$N$$$ integers $$$A_1, A_2, \ldots, A_N$$$, where $$$1 \leq A_i \leq 1000$$$.

You may choose any integer $$$X$$$ ($$$1 \leq X \leq 1000$$$) and any range $$$1 \leq L \leq R \leq N$$$. You must perform the operation exactly once.

Output

Print a single integer $$$E$$$, the maximum possible number of even numbers in the array after the operation.

Examples
Input
3
1 2 3
Output
2
Input
14
1 2 2 1 1 1 2 1 1 2 2 2 1 1
Output
10
Input
1
1000
Output
1