output_description: Print the minimum possible unbalancedness of S'.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      S
attempt: S = input()
  
  max0 = 0
  max1 = 0
  amax0 = []
  amax1 = []
  mi0 = 0
  mi1 = 0
  h0 = 0
  h1 = 0
  for i, c in enumerate(S):
      if c == "1":
          h1 += 1
          if h1 - mi1 > max1:
              max1 = h1 - mi1
              amax1 = [i]
          elif h1 - mi1 == max1:
              amax1.append(i)
          h0 -= 1
          if h0 < mi0:
              mi0 = h0
      elif c == "0":
          h1 -= 1
          if h1 < mi1:
              mi1 = h1
          h0 += 1
          if h0 - mi0 > max0:
              max0 = h0 - mi0
              amax0 = [i]
          elif h0 - mi0 == max0:
              amax0.append(i)
      else:
          h1 -= 1
          if h1 < mi1:
              mi1 = h1
          h0 -= 1
          if h0 < mi0:
              mi0 = h0
  if max0 < max1:
      if len(set([i % 2 for i in amax1])) == 1:
          print(max1)
      else:
          print(max1 + 1)
  elif max0 > max1:
      if len(set([i % 2 for i in amax0])) == 1:
          print(max0)
      else:
          print(max0 + 1)
  else:
      if len(set([i % 2 for i in amax1] + [(max0 + i) % 2 for i in amax0])) == 1:
          print(max0)
      else:
          print(max0 + 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"}]