問題文

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 に置き換える。

制約

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

入力

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

$S$

出力

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

入力例 1

010

出力例 1

2

以下の操作で、$S$ の要素をすべて 0 にできます。

• 長さ $3$ の区間 \[1,3\] に操作を行う。$S$ は 101 になる。
• 長さ $2$ の区間 \[1,2\] に操作を行う。$S$ は 011 になる。
• 長さ $2$ の区間 \[2,3\] に操作を行う。$S$ は 000 になる。

入力例 2

100000000

出力例 2

8

入力例 3

00001111

出力例 3

4