P15806 [JOI 2013 Final] 彩灯 / Illumination

JOI 高校的文化祭每年都会在走廊上装饰彩灯。彩灯由 $N$ 个灯泡组成，灯泡沿着走廊从西到东排成一列。每个灯泡要么亮着，要么灭着。 JOI 高校的仓库里沉睡着一台可以操作灯泡的机器。这台机器可以指定彩灯中一段连续的灯泡，然后将指定范围内所有亮着的灯泡熄灭，并将所有灭着的灯泡点亮。但是，由于机器老化，它只能被使用一次。 JOI 高校的学生们喜欢亮灯和灭灯的灯泡交替排列的序列（这样的灯泡序列被称为**交替序列**）。因此，他们决定在必要时最多使用一次这台机器，以制作出一个包含尽可能长的交替序列的彩灯。 例如，假设彩灯的初始状态从西到东如下所示（○ 表示亮着的灯泡，● 表示灭着的灯泡）： :::align{center}  ::: 此时，如果对第 4 个到第 7 个的 4 个灯泡使用机器，则变为： :::align{center}  ::: 这样，从第 2 个到第 8 个的灯泡就构成了一个长度为 7 的交替序列。 :::align{center}  ::: 另外，如果只对第 8 个灯泡使用机器，则变为： :::align{center}  ::: 这样，从第 4 个到第 10 个的灯泡就构成了一个长度为 7 的交替序列。 :::align{center}  ::: 最多使用一次机器，无法制造出长度达到 8 或以上的交替序列。 ### 任务 给定彩灯的信息，编写一个程序，求出在最多使用一次机器的情况下，所能得到的灯泡序列中包含的交替序列长度的最大值。

从标准输入读取以下数据。 - 第一行包含一个整数 $N$。 - 第二行包含 $N$ 个用空格分隔的 0 或 1。每个整数表示在操作机器前灯泡的状态。从左数第 $i$ ($1 \leq i \leq N$) 个整数表示从西侧数第 $i$ 个灯泡的信息，整数为 1 表示灯泡亮着，为 0 表示灯泡灭着。

向标准输出输出一行，包含一个整数，表示可以制作出的灯泡序列中所含交替序列长度的最大值。

### 样例解释 1. 这是题目描述中说明的例子。 2. 如果只操作从西侧数第 4 个灯泡，可以得到满足最大值 8 的交替序列。 3. 如果操作从西侧数第 2 个到第 4 个的灯泡，可以制作出包含所有灯泡的交替序列。 4. 请注意，有时可能不需要使用机器。 ### 限制 $2 \leq N \leq 100\,000$　构成彩灯的灯泡个数。 ### 评分标准 在评分数据中，占分值 20% 的部分满足 $N \leq 500$。 在评分数据中，占分值 40% 的部分满足 $N \leq 2000$。 --- 翻译由 DeepSeek V3.2 完成