JOI 高校的文化节上，每年都会在走廊上装饰电灯。电灯由 $N$ 个灯泡组成，这些灯泡排列在走廊的西侧到东侧。每个灯泡都有两种状态：亮着或者熄灭。

在 JOI 高校的仓库里，有一台操作灯泡的机器正在休眠。这台机器可以指定连续的一段灯泡，在这些被指定的灯泡中，将亮着的灯泡都变成熄灭状态，将熄灭的灯泡都变成亮着状态。然而，由于机器老化的原因，它只能使用一次。

JOI 高校的学生们喜欢亮着的灯泡和熄灭的灯泡交替排列的序列（我们称之为交替序列）。因此，他们决定在需要的情况下最多使用一次这台机器，来制作一个包含尽可能长的交替序列的电灯装饰。

示例

例如，假设电灯的布局从西向东如下所示：

○ ○ ● ● ○ ● ○ ○ ○ ●

其中， ○ 表示亮着的灯泡，● 表示熄灭的灯泡。在这种情况下，如果对第 4 到第 7 个灯泡进行机器操作，则结果如下：

○ ○ ● ○ ● ○ ●