B - 01 Unbalanced /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 800

問題文

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

S に含まれる全ての ?01 に変えて(? ごとに変換後の文字を選択できます),文字列 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

Score : 800 points

Problem Statement

Given is a string S, where each character is 0, 1, or ?.

Consider making a string S' by replacing each occurrence of ? with 0 or 1 (we can choose the character for each ? independently). Let us define the unbalancedness of S' as follows:

  • (The unbalancedness of S') = \max \{ The absolute difference between the number of occurrences of 0 and 1 between the l-th and r-th character of S (inclusive) :\ 1 \leq l \leq r \leq |S|\}

Find the minimum possible unbalancedness of S'.

Constraints

  • 1 \leq |S| \leq 10^6
  • Each character of S is 0, 1, or ?.

Input

Input is given from Standard Input in the following format:

S

Output

Print the minimum possible unbalancedness of S'.


Sample Input 1

0??

Sample Output 1

1

We can make S'= 010 and achieve the minimum possible unbalancedness of 1.


Sample Input 2

0??0

Sample Output 2

2

Sample Input 3

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

Sample Output 3

4