题目描述

0 と 1 からなる文字列 $S$ が与えられます。 以下の操作を好きな回数繰り返すことで $S$ の要素をすべて 0 にできるような、$|S|$ 以下の最大の整数 $K$ を求めてください。

• $S$ の長さ $K$ 以上の連続する区間 $[l,r]$ を選ぶ(すなわち、$r-l+1\geq\ K$ が満たされる必要がある)。$l\leq\ i\leq\ r$ なるすべての整数 $i$ に対し、$S_i$ が 0 なら $S_i$ を 1 に、$S_i$ が 1 なら $S_i$ を 0 に置き換える。

输入格式

入力は以下の形式で標準入力から与えられる。

$S$

输出格式

操作を好きな回数繰り返すことで $S$ の要素をすべて 0 にできるような 最大の (21:08 JST 修正) 整数 $K$ を出力せよ。

题目大意

给出一个由0和1组成的字符串S。求不大于S的最大整数K，这样我们可以通过多次重复下面的操作将S的所有字符都变成0。

选择S中长度至少为K(即必须满足r-l+1≥K)的连续段[l,r]。对于l≤i≤r的每个整数i，执行以下操作：如果S_i为0，则用1替换；如果S_i为1，则用0替换。

010

2

100000000

8

00001111

4

提示

制約

• $1\leq\ |S|\leq\ 10^5$
• $S_i(1\leq\ i\leq\ N)$ は 0 または 1 である

Sample Explanation 1

以下の操作で、$S$ の要素をすべて 0 にできます。 - 長さ $3$ の区間 $[1,3]$ に操作を行う。$S$ は 101 になる。 - 長さ $2$ の区間 $[1,2]$ に操作を行う。$S$ は 011 になる。 - 長さ $2$ の区間 $[2,3]$ に操作を行う。$S$ は 000 になる。