#include <bits/stdc++.h>
using namespace std;
long long ans = (1 << 29);
long long cnt[2][1100000];
long long solve(long long mini, long long maxi, string s) {
  long long bottom = 0, top = 0;
  bool only = true;
  for (int i = s.size() - 1; i >= 0; i--) {
    cnt[0][i] = cnt[0][i + 1];
    cnt[1][i] = cnt[1][i + 1];
    if (s[i] == '0') cnt[0][i]++;
    if (s[i] == '1') cnt[1][i]++;
  }
  int now = -1;
  for (char c : s) {
    now++;
    if (c == '0') {
      only = false;
      bottom--;
      top--;
      mini = min(mini, top);
      bottom = max(bottom, mini);
      if ((bottom - top) % 2 != 0) {
        if (cnt[0][now + 1] == 0)
          ans =
              min(ans, max(maxi, bottom - 1 + ((long long)s.size() - now - 1)) -
                           (bottom - 1));
        bottom++;
      }
    }
    if (c == '1') {
      only = false;
      bottom++;
      top++;
      maxi = max(maxi, bottom);
      top = min(top, maxi);
      if ((bottom - top) % 2 != 0) {
        ans =
            min(ans,
                top + 1 - min(mini, top + 1 - ((long long)s.size() - now - 1)));
        top--;
      }
    }
    if (c == '?') {
      if (only) continue;
      top++;
      bottom--;
      top = min(top, maxi);
      if ((bottom - top) % 2 != 0) top--;
      bottom = max(bottom, mini);
      if ((bottom - top) % 2 != 0) bottom++;
    }
  }
  ans = min(ans, maxi - mini);
  if (only)
    return 1;
  else
    return ans;
}
int main() {
  string s;
  cin >> s;
  cout << min({solve(0, 0, s), solve(0, 1, s), solve(-1, 0, s),
               solve(-1, 1, s)})
       << endl;
  return 0;
}
