program zero_one_unbalanced
  implicit none
  character(1000000) :: s = ''
  integer :: n, i
  integer, dimension(0:1000000) :: a = 0, x = 0
  read(*,'(a)') s
  n = len_trim(s)
  do i = 1, n
    a(i) = a(i - 1) + merge(1, -1, s(i:i) == '1')
  end do
  x(n) = a(n)
  do i = n - 1, 0, -1
    x(i) = max(x(i + 1), a(i))
  end do
  write(*,'(i0)') min(x(0) - f(x(0)), x(0) + 1 - f(x(0) + 1))
contains
  integer function f(m) result(res)
    integer, intent(in) :: m
    integer :: p, i
    p = 0
    do i = 1, n
      if (s(i:i) == '?') then
        if (x(i) + 2 * (p + 1) <= m) then
          a(i) = a(i - 1) + 1
          p = p + 1
        else
          a(i) = a(i - 1) - 1
        end if
      else
        a(i) = a(i - 1) + merge(1, -1, s(i:i) == '1')
      end if
    end do
    res = minval(a(0:n))
  end
end program zero_one_unbalanced