output_description: Print the minimum possible unbalancedness of S'.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      S
attempt: def solve(S):
      if S[0] == "?":
          for i in range(len(S)):
              if S[i] == "0":
                  if i % 2 == 0:
                      S[0] = "0"
                  else:
                      S[0] = "1"
                  break
              elif S[i] == "1":
                  if i % 2 == 0:
                      S[0] = "1"
                  else:
                      S[0] = "0"
                  break
      if S[0] == "?":
          return 1
  
      sum0 = 0
      sum1 = 0
      un = 1
      val = -1
      for i in range(len(S)):
          if S[i] == "0":
              sum0 += 1
              val = -1
          elif S[i] == "1":
              sum1 += 1
              val = -1
          else:
              if sum0 > sum1:
                  sum1 += 1
              elif sum1 > sum0:
                  sum0 += 1
              else:
                  if val == -1:
                      for j in range(i, len(S)):
                          if S[j] == "0":
                              if (j - i) % 2 == 0:
                                  val = 0
                              else:
                                  val = 1
                              break
                          elif S[j] == "1":
                              if (j - i) % 2 == 0:
                                  val = 1
                              else:
                                  val = 0
                              break
                  if val == 1:
                      sum1 += 1
                  elif val == 0:
                      sum0 += 1
                  else:
                      return un
          un = max(un, abs(sum0 - sum1))
      return un
  
  
  S = list(input())
  print(min(solve(S), solve(S[::-1])))
  
problem_description: 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'.
samples: [{"input": "0??", "output": "1\n    \n\nWe can make S'= `010` and achieve the minimum possible unbalancedness of 1.\n\n* * *"}, {"input": "0??0", "output": "2\n    \n\n* * *"}, {"input": "??00????0??0????0?0??00??1???11?1?1???1?11?111???1", "output": "4"}]