{"raw_statement":[{"iden":"problem statement","content":"Given is a string $S$, where each character is `0`, `1`, or `?`.\nConsider 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:\n\n*   (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|}$\n\nFind the minimum possible unbalancedness of $S'$."},{"iden":"constraints","content":"*   $1 \\leq |S| \\leq 10^6$\n*   Each character of $S$ is `0`, `1`, or `?`."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$S$"},{"iden":"sample input 1","content":"0??"},{"iden":"sample output 1","content":"1\n\nWe can make $S'=$ `010` and achieve the minimum possible unbalancedness of $1$."},{"iden":"sample input 2","content":"0??0"},{"iden":"sample output 2","content":"2"},{"iden":"sample input 3","content":"??00????0??0????0?0??00??1???11?1?1???1?11?111???1"},{"iden":"sample output 3","content":"4"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}