AT_agc045_b [AGC045B] 01 Unbalanced

[problemUrl]: https://atcoder.jp/contests/agc045/tasks/agc045_b 文字列 $ S $ が与えられます． $ S $ の各文字は，`0`,`1`,`?` のいずれかです． $ S $ に含まれる全ての `?` を `0` か `1` に変えて（`?` ごとに変換後の文字を選択できます），文字列 $ S' $ を作ることを考えます． ここで，$ S' $ のアンバランス度を，次のように定義します． - $ S' $ のアンバランス度 $ =\ \max\ \{\ S' $ の $ l $ 文字目から $ r $ 文字目までに含まれる `0` の個数と `1` の個数の差の絶対値 $ :\ 1\ \leq\ l\ \leq\ r\ \leq\ |S|\} $ $ S' $ のアンバランス度としてありうる最小の値を求めてください．

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

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

### 制約 - $ 1\ \leq\ |S|\ \leq\ 10^6 $ - $ S $ の各文字は `0`,`1`,`?` のいずれかである． ### Sample Explanation 1 $ S'= $`010` とすれば，アンバランス度は $ 1 $ になり，これが最小です．