题目描述

彩灯由 $N$ 个灯泡组成，灯泡沿着走廊从西到东排成一列。每个灯泡要么亮着，要么灭着。

现在你可以指定一个连续的区间的灯泡进行翻转。即将指定范围内所有亮着的灯泡熄灭，并将所有灭着的灯泡点亮。（注意只允许指定一次）

学生们喜欢亮灯和灭灯的灯泡交替排列的序列（这样的灯泡序列被称为交替序列）。因此，你决定在必要时最多使用一次这台机器，以制作出一个包含尽可能长的交替序列的彩灯。

给定彩灯的信息，编写一个程序，求出在最多使用一次机器的情况下，所能得到的灯泡序列中包含的交替序列长度的最大值。

输入格式

第一行包含一个整数 $N$。

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

输出格式

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

10
1 1 0 0 1 0 1 1 1 0

7

10
1 0 0 0 0 1 0 1 0 1

8

5
1 1 0 1 1

5

3
0 1 0

3

提示

样例 1 解释

• 初始灯泡序列为：$[1,1,0,0,1,0,1,1,1,0]$
• 翻转区间 $[4,7]$ 的灯泡得到 $[1,1,0,1,0,1,0,1,1,0]$。

此时区间 $[2,8]$ 形成一个长度为 $7$ 的交替序列。可以证明不存在答案更大的情况。

数据范围

• $20\%$ 的数据满足 $2 \leq N \leq 500$。
• $40\%$ 的数据满足 $2 \leq N \leq 2000$。
• $100\%$ 的数据满足 $2 \leq N \leq 10^5$。