题目描述

给你一个长度为 $n$ 的 01 串 $s$，你可以进行操作：

选择一个操作集合 $U\subseteq \left\{0,1,\cdots,n\right\}(可以是空集)$ ，然后每次选择一个最大的 $x\in U$ 并将其从 $U$ 中删去，然后将 $s[1,x]$ 按位取反，将 $s[x+1,n]$ 翻转。 注意 $s[1,x]$ 和 $s[x+1,n]$ 都可以为空子串。

定义一个字符串 $s$ 的价值为其满足相邻位不同的最长子段长度， 现在要求你选择一个操作集合，最大化操作完成后字符串 $s$ 的价值，你只需要输出字符串的价值。

输入格式

给出一行 字符串$s$ $($只包含$0/1$$)$

输出格式

输出一行一个整数，表示答案

样例 #1

样例输入 #1

01111

样例输出 #1

3

样例 #2

样例输入 #2

10001

样例输出 #2

3

样例 #3

样例输入 #3

10001011101000001001

样例输出 #3

11

提示

定义$n$为输入数据的长度

Subtask 1 (10pts): $n \leq20$

Subtask 2 (20pts): $n \leq300$

Subtask 3 (20pts): $n \leq5000$

Subtask 4 (50pts): 无特殊限制

对于 $100 \%$ 的数据 $n \leq 10^7$

下面给出一种样例一最优解的构造:

选取集合$U=\{1,4,5\}$

第一步 将$[1,5]$取反，$[6,5]$空区间不合法，序列变为$[1,0,0,0,0]$

第二步 将$[1,4]$取反，$[5,5]$翻转,序列变为$[0,1,1,1,0]$

第三步 将$[1,1]$取反，$[2,5]$翻转，序列变为$[1,0,1,1,1]$

可以发现$[1,3]$为符合题目要求的子段，答案为3。

可以证明，不存在更优的解