問題文

文字列 $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'$ のアンバランス度としてありうる最小の値を出力せよ．

入力例 1

0??

出力例 1

1

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

入力例 2

0??0

出力例 2

2

入力例 3

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

出力例 3

4