题目背景

试题来源：https://koi.or.kr/archives/。中文翻译做了少量本土化修改。

按照署名—非商业性使用—相同方式共享 4.0 协议国际版进行授权。

题目描述

有 $N$ 个自然数从左到右依次排列。第 $i$（$1 \leq i \leq N$）个位置上的自然数为 $A_i$。

你可以从中任选若干个自然数。注意，不能一个自然数也不选，必须至少选择 1 个自然数。

设你选择的自然数个数为 $k$，选择的自然数为 $B_1, B_2, \cdots, B_k$。所选自然数的顺序应保持其在原序列中的相对顺序。

例如，若 $N = 5$，且 $A = [3, 1, 4, 1, 5]$，你选择了第 2、4、5 个位置上的自然数，则 $k = 3$，$B = [1, 1, 5]$。

将 $B$ 中相邻两个自然数的和计算出来：第一个和第二个，第二个和第三个，第三个和第四个，……，如果所有的和都是奇数，那么称 $B$ 是一个不稳定数列。当 $k = 1$ 时，特殊地，$B$ 被认为是不稳定数列。

例如，若 $k = 6$，$B = [1, 4, 3, 2, 5, 4]$，那么：

• 第一个自然数（1）与第二个自然数（4）的和为 5，为奇数；
• 第二个自然数（4）与第三个自然数（3）的和为 7，为奇数；
• 第三个自然数（3）与第四个自然数（2）的和为 5，为奇数；
• 第四个自然数（2）与第五个自然数（5）的和为 7，为奇数；
• 第五个自然数（5）与第六个自然数（4）的和为 9，为奇数。

因此，相邻两个自然数的和始终为奇数，$B$ 是不稳定数列。

又如，$k = 1$，$B = [2]$，由于 $k = 1$，故 $B$ 是不稳定数列。

但是，若 $k = 4$，$B = [4, 5, 1, 2]$，那么：

• 第一个自然数（4）与第二个自然数（5）的和为 9，为奇数；
• 第二个自然数（5）与第三个自然数（1）的和为 6，为偶数。

因为存在相邻两个自然数的和不是奇数的情况，所以 $B$ 不是不稳定数列。

你的任务是：选择若干个自然数，使得所构成的 $B$ 是不稳定数列，并且所选自然数的个数 $k$ 最大。请编写一个程序，求出这个最大的 $k$。

例如，当 $A = [4, 5, 1, 2]$ 时：

• 如果选取全部的自然数，得到 $B = [4, 5, 1, 2]$，这不是不稳定数列，不能用全部 4 个数；
• 但若选取第 1、3、4 个自然数，得到 $B = [4, 1, 2]$：
  • 第一个自然数（4）与第二个自然数（1）的和为 5，为奇数；
  • 第二个自然数（1）与第三个自然数（2）的和为 3，为奇数。

因此，所选 $B$ 是不稳定数列，且长度为 3，是可能的最大值。

输入格式

第一行输入一个整数 $N$。

第二行输入 $A_1, A_2, \cdots, A_N$，各数之间用空格分隔。

输出格式

输出一个整数，表示可以选择的最大自然数个数 $k$。

4
4 5 1 2

3

3
3 2 3

3

5
3 3 3 3 3

1

提示

限制条件

• 所有给定数均为自然数。
• $1 \leq N \leq 300\,000$
• $1 \leq A_i \leq 100\,000 \quad (1 \leq i \leq N)$

子任务

1. （5 分）答案为 $N - 1$ 或 $N$。
2. （8 分）$N \leq 15$
3. （12 分）$N \leq 5\,000$
4. （15 分）$A_i \leq 50 \quad (1 \leq i \leq N)$
5. （60 分）无附加限制。

翻译由 ChatGPT-4o 完成