配点: 100 点
每年的JOI高中学园祭,走廊都会被灯光装饰。照度为 它由 N 个灯泡组成,灯泡从走廊的西侧到东侧排成一排。每个灯泡要么打开,要么关闭。
JOI 高中仓库里有一台操作灯泡的机器。当本机在灯光装饰中指定连续的灯泡时,所有指定的点亮的灯泡将被关闭,而所有未点亮的灯泡将被打开。但由于机器老化, 只能使用1 次。
JOI 高中生正在学习如何制作成排的灯泡,这些灯泡在点亮和熄灭之间交替。 我喜欢交互列)。因此,如果您需要这台机器, 我决定仅使用 1 次来创建包含尽可能多的交替行的照明。
例
例如,灯光的排列是从西向东。
○ ○ ● ● ○ ● ○ ○ ○ ●
(○代表灯泡亮,●代表灯泡不亮)。 此时,4 起 件数最多为 7 当使用 4 灯泡操作机器时,
○ ○ ● ○ ● ○ ● ○ ○ ●
变为2 起 件数最多为 8 灯泡的长度是 形成 7 的交替序列。
○ ○ ● ○ ● ○ ● ○ ○ ●
另外, 如果我们只为第8 个灯泡操作机器, 直到
○ ○ ● ● ○ ● ○ ● ○ ●
变为4 起 件数最多为 10 的灯泡形成长度为 7 的交替行。
○ ○ ● ● ○ ● ○ ● ○ ●
最大化机器 通过使用 1 次,长度变为 无法创建超过 8 个交替列。
課題
当给出有关照明的信息时,机器设置为最大 1 编写一个程序,求使用一次灯泡获得的灯泡阵列中包含的交替行的最大可能长度。
制限
| 2 \leqq N \leqq 100\,000 | 构成照明的灯泡数量 |
入力
从标准输入读取以下数据。
- 1 行是整数 N 被写下了。
- 第二行说 N 的 您可以创建一个包含 0 或 至少 1 以空格作为分隔符。每个整数代表操作机器之前有关灯泡的信息。从左边开始 i (1 \leqq i \leqq N) 从西数第一个整数 代表第 i 个灯泡的信息,整数为 1 然后灯泡亮了,0 表示灯不亮。
出力
将标准输出设置为一个整数,表示可以创建的交替灯泡行的最大长度。 输出为 1 行输出。
採点基準
评分数据中,分配的分数 20 对于%,N \leqq 500 很满意。
评分数据中,分配的分数 40 对于%,N \leqq 2\,000 很满意。
入力例 1
10 1 1 0 0 1 0 1 1 1 0
出力例 1
7
这是问题文本中解释的示例。
入力例 2
10 1 0 0 0 0 1 0 1 0 1
出力例 2
8
从西边 如果仅操作第 4 个灯泡,则最大值 获得满足 8 的交替序列。
入力例 3
5 1 1 0 1 1
出力例 3
5
从西边算起 通过操作最多 2 起 件数最多为 4 个灯泡,您可以创建所有灯泡的交替行。
入力例 4
3 0 1 0
出力例 4
3
请注意,有时您不需要使用机器。