불안정한 수열

$N$개의 자연수가 좌우 일렬로 놓여 있다. 왼쪽에서 $i$ ($1 \le i \le N$)번째 자연수는 $A_i$이다.

여러분은 이 중에서 원하는 만큼 자연수를 고를 수 있다. 단, 아무 자연수도 고르지 않을 수는 없으며, 반드시 1개 이상을 골라야 한다.

고른 자연수의 개수를 $k$라고 하고, 고른 자연수를 $B_1, B_2, \cdots, B_k$라고 하자. 고른 자연수의 순서는 원래 놓여 있던 순서를 그대로 유지한다.

예를 들어, $N = 5$, $A = [3, 1, 4, 1, 5]$라고 하자. 왼쪽에서 두 번째, 네 번째, 다섯 번째 자연수를 고르면 $k = 3$이고 $B = [1, 1, 5]$가 된다.

$B$에서 이웃한 두 자연수의 합, 즉 $B_1$과 $B_2$의 합, $B_2$와 $B_3$의 합, ...을 구했을 때 항상 홀수이면 $B$를 불안정한 수열이라고 하자. $k = 1$이면 $B$는 불안정한 수열이라고 본다.

예를 들어, $k = 6$, $B = [1, 4, 3, 2, 5, 4]$이면 이웃한 합은 순서대로 5, 7, 5, 7, 9이다. 모두 홀수이므로 $B$는 불안정한 수열이다.

또한 $k = 1$, $B = [2]$이면 $k = 1$이므로 $B$는 불안정한 수열이다.

하지만 $k = 4$, $B = [4, 5, 1, 2]$이면 첫 번째 합 9는 홀수이지만 5와 1의 합 6은 짝수이다. 이웃한 합이 홀수가 아닌 곳이 있으므로 $B$는 불안정한 수열이 아니다.

$B$가 불안정한 수열이 되도록 하면서, 가장 많은 개수의 자연수를 골라야 한다. 이때 최대 몇 개의 자연수를 고를 수 있는지 구하는 프로그램을 작성하라.

예를 들어, $A = [4, 5, 1, 2]$일 때를 보자. 네 개를 모두 고르면 $B = [4, 5, 1, 2]$가 되고 불안정한 수열이 아니므로 네 개는 불가능하다. 왼쪽에서 첫 번째, 세 번째, 네 번째 자연수를 고르면 $B = [4, 1, 2]$가 된다. 4와 1의 합 5, 1과 2의 합 3이 모두 홀수이므로 $B$는 불안정한 수열이다. 따라서 최대는 3개이다.

첫 번째 줄에 $N$이 주어진다.

두 번째 줄에 $A_1, A_2, \cdots, A_N$이 공백을 사이에 두고 차례대로 주어진다.

첫 번째 줄에 답을 출력한다.

• 주어지는 모든 수는 자연수이다.
• $1 \le N \le 300\,000$
• $1 \le A_i \le 100\,000$ ($1 \le i \le N$)