题目描述

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

题目大意

给定一个由 $0$ , $1$ 和 $?$ 组成的字符串，对于这个这个字符串，我们可以选择将 $?$ 变成 $0$ 或 $1$ 。我们规定这个字符串的不平衡度为 $S$ 。$S$ 满足 $S = max \left\{l到r中0的个数和1的个数的差的绝对值\right\}(1 \leq l,r \leq len)$

你需要最小化最大的平衡度

0??

1

0??0

2

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

4

提示

制約

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

Sample Explanation 1

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