#include <bits/stdc++.h>
using namespace std;
int solve(string const& s, int h) {
  int n = s.size();
  vector<pair<int, int> > dp(n + 1, {0, h});
  for (int i = n - 1, par = -1; i >= 0; i--) {
    if (par != -1) par ^= 1;
    if (s[i] == '1') {
      dp[i] = {dp[i + 1].first - 1, dp[i + 1].second - 1};
    } else if (s[i] == '0') {
      dp[i] = {dp[i + 1].first + 1, dp[i + 1].second + 1};
    } else {
      if (dp[i + 1].first == dp[i + 1].second && par == -1) {
        assert(dp[i + 1].first == 0 || dp[i + 1].first == h);
        if (dp[i + 1].first == 0) {
          par = 1;
        } else {
          par = (h - 1) & 1;
        }
      }
      dp[i] = {dp[i + 1].first - 1, dp[i + 1].second + 1};
    }
    dp[i].first = max(dp[i].first, 0);
    dp[i].second = min(dp[i].second, h);
    if ((dp[i].first > h) || (dp[i].second < 0) ||
        (par != -1 && dp[i].first == dp[i].second &&
         (dp[i].first & 1) != par)) {
      return 0;
    }
  }
  return 1;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  string s;
  cin >> s;
  int n = s.size();
  int l = 0, r = n - 1;
  while (l != r) {
    int mid = (l + r) / 2;
    int ok = solve(s, mid);
    if (ok) {
      r = mid;
    } else
      l = mid + 1;
  }
  cout << l << '\n';
  return 0;
}
