← 返回题目列表

Codeforces · 603/A

A. 另类思维

中文机器翻译题面 查看原题

Kevin 刚刚在美国奶牛识别奥林匹克竞赛 (USAICO) 上收到了令人失望的结果,结果是长度为 n 的二进制字符串。 Kevin 字符串中的每个字符代表 Kevin 在奥林匹克竞赛 n 个问题之一上的得分 - '1' 表示正确识别的牛,否则为 '0'。

然而,一切并没有失去。凯文是另类思维的大力支持者,他认为他的分数不应该是他的分数的总和,而应该是他的字符串的最长交替子序列的长度。在这里,我们将字符串的交替子序列定义为不一定连续的子序列,其中没有两个连续元素相等。例如,{0, 1, 0, 1}、{1, 0, 1} 和 {1, 0, 1, 0} 是交替序列,而 {1, 0, 0} 和 {0, 1, 0, 1, 1} 则不是。

Kevin,作为一个狡猾的小马勃,愿意侵入 USAICO 数据库以提高他的分数。为了巧妙起见,他决定翻转一个子串,即取乐谱中的一个连续的非空子串,并将该子串中的所有“0”更改为“1”,反之亦然。经过这样的操作后,凯文想知道他的字符串可能具有的最长可能交替子序列的长度。

输入

第一行包含奥林匹克题数 n (1 ≤ n ≤ 100 000)。

以下行包含长度为 n 的二进制字符串,表示 Kevin 在 USAICO 上的结果。

输出

输出一个整数,即 Kevin 在翻转单个子字符串后可以在字符串中创建的最长可能交替子序列的长度。

示例

输入 #1

8
10000011

输出 #1

5

输入 #2

2
01

输出 #2

2

注意

在第一个示例中,Kevin 可以翻转粗体子字符串“10000011”并将其字符串转换为“10011011”,该字符串具有长度为 5 的交替子序列:“10011011”。

在第二个样本中,Kevin 可以翻转整个字符串并且仍然具有相同的分数。