配点 : $800$ 点

問題文

文字列 $S$ が与えられます． $S$ の各文字は，0,1,? のいずれかです．

$S$ に含まれる全ての ? を 0 か 1 に変えて（? ごとに変換後の文字を選択できます），文字列 $S'$ を作ることを考えます． ここで，$S'$ のアンバランス度を，次のように定義します．

• $S'$ のアンバランス度 $= \max \{ S'$ の $l$ 文字目から $r$ 文字目までに含まれる 0 の個数と 1 の個数の差の絶対値 $:\ 1 \leq l \leq r \leq |S|\}$

$S'$ のアンバランス度としてありうる最小の値を求めてください．

制約

• $1 \leq |S| \leq 10^6$
• $S$ の各文字は 0,1,? のいずれかである．

入力

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

$S$

出力

$S'$ のアンバランス度としてありうる最小の値を出力せよ．

0??

1

$S'=$010 とすれば，アンバランス度は $1$ になり，これが最小です．

0??0

2

??00????0??0????0?0??00??1???11?1?1???1?11?111???1

4