#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 1;
int n, pref[N];
string s;
vector<int> prefv[4 * N];
bool solve(int diff) {
  int pos = 0, neg = 0;
  vector<int> ind(4 * n + 1);
  for (int i = 1; i <= n; ++i) {
    if (s[i - 1] == '0') {
      pos = max(0, pos - 1);
      neg = neg + 1;
    } else if (s[i - 1] == '1') {
      pos = pos + 1;
      neg = max(0, neg - 1);
    } else {
      int j = n + 1;
      int idx = neg - diff - 1 + pref[i - 1] + 2 * n;
      if (ind[idx] < (int)prefv[idx].size()) {
        j = prefv[idx][ind[idx]];
      }
      bool fail = 0;
      int indx = diff - pos - 1 + pref[i - 1] + 2 * n;
      if (diff - pos - 1 < 0 ||
          (ind[indx] < (int)prefv[indx].size() && prefv[indx][ind[indx]] < j)) {
        fail = 1;
      }
      if (fail || j == n + 1) {
        pos = max(0, pos - 1);
        neg = neg + 1;
      } else {
        pos = pos + 1;
        neg = max(0, neg - 1);
      }
    }
    if (pos > diff || neg > diff) return false;
    ind[pref[i] + 2 * n]++;
  }
  return true;
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> s;
  n = s.size();
  for (int i = 1; i <= n; ++i) {
    if (s[i - 1] == '0' || s[i - 1] == '?') {
      pref[i] = pref[i - 1] - 1;
    } else {
      pref[i] = pref[i - 1] + 1;
    }
    prefv[2 * n + pref[i]].push_back(i);
  }
  int lo = 1, hi = n - 1, mid, res = n;
  while (lo <= hi) {
    mid = (lo + hi) / 2;
    if (solve(mid)) {
      hi = mid - 1;
      res = mid;
    } else {
      lo = mid + 1;
    }
  }
  cout << res;
}
