#include <bits/stdc++.h>
using namespace std;
template <typename T>
struct lazysegtree {
  int n;
  vector<pair<int, int> > dat;
  vector<int> lazy;
  lazysegtree(int n_ = 0) {
    n = 1;
    while (n < n_) n <<= 1;
    dat.assign(2 * n - 1, make_pair(-1e7, 1e7));
    lazy.assign(2 * n - 1, 0);
  }
  void update(int a, int b, int x, int k = 0, int l = 0, int r = -1) {
    if (r < 0) r = n;
    if (b <= l || r <= a)
      return;
    else if (a <= l && r <= b) {
      lazy[k] += x;
    } else {
      update(a, b, x, 2 * k + 1, l, (l + r) / 2);
      update(a, b, x, 2 * k + 2, (l + r) / 2, r);
      dat[k].first = max(dat[2 * k + 1].first + lazy[2 * k + 1],
                         dat[2 * k + 2].first + lazy[2 * k + 2]);
      dat[k].second = max(dat[2 * k + 1].second + lazy[2 * k + 1],
                          dat[2 * k + 2].second + lazy[2 * k + 2]);
    }
  }
  pair<int, int> query(int a, int b, int k = 0, int l = 0, int r = -1) {
    if (r < 0) r = n;
    if (b <= l || r <= a)
      return make_pair(0, 0);
    else if (a <= l && r <= b) {
      return make_pair(dat[k].first + lazy[k], dat[k].second + lazy[k]);
    } else {
      pair<int, int> A = query(a, b, 2 * k + 1, l, (l + r) / 2),
                     B = query(a, b, 2 * k + 2, (l + r) / 2, r);
      A.first = max(A.first, B.first) + lazy[k];
      A.second = min(A.second, B.second) + lazy[k];
      return A;
    }
  }
};
string S;
bool check(int lim) {
  int now1 = 0, now0 = 0;
  stack<int> Q;
  vector<int> A0(S.size() + 1), A1(S.size() + 1);
  stack<pair<int, int> > m0, m1;
  m0.push(make_pair(0, 0));
  m1.push(make_pair(0, 0));
  for (int i = 0; i < S.size(); i++) {
    if (S[i] == '0') {
      now1--;
      now0--;
    } else if (S[i] == '1') {
      now1++;
      now0++;
    } else {
      now1++;
      now0--;
      Q.push(i + 1);
    }
    bool f1 = true, f2 = true;
    while (f1 && now1 - m1.top().first == -lim ||
           f2 && now0 - m0.top().first == lim) {
      if (f1 && now1 - m1.top().first == -lim) {
        int id = m1.top().second;
        vector<int> del;
        while (!Q.empty() && Q.top() > id) {
          int j = Q.top();
          Q.pop();
          now0 += 2;
          del.push_back(j);
        }
        reverse(del.begin(), del.end());
        vector<pair<int, int> > dm;
        while (m0.top().second > id) {
          dm.push_back(m0.top());
          m0.pop();
        }
        int k = 0;
        for (int j = dm.size(); j--;) {
          while (k < del.size() && del[k] <= dm[j].second) k++;
          int X = dm[j].first + k * 2;
          if (m0.top().first > X) m0.push(make_pair(X, dm[j].second));
        }
        f1 = false;
        f2 = true;
      } else {
        int id = m0.top().second;
        vector<int> del;
        while (!Q.empty() && Q.top() > id) {
          int j = Q.top();
          Q.pop();
          now1 -= 2;
          del.push_back(j);
        }
        reverse(del.begin(), del.end());
        vector<pair<int, int> > dm;
        while (m1.top().second > id) {
          dm.push_back(m1.top());
          m1.pop();
        }
        int k = 0;
        for (int j = dm.size(); j--;) {
          while (k < del.size() && del[k] <= dm[j].second) k++;
          int X = dm[j].first - k * 2;
          if (m1.top().first < X) m1.push(make_pair(X, dm[j].second));
        }
        f2 = false;
        f1 = true;
      }
    }
    if (now1 - m1.top().first < -lim || now0 - m0.top().first > lim)
      return false;
    A0[i + 1] = now0;
    if (m0.top().first > now0) m0.push(make_pair(now0, i + 1));
    A1[i + 1] = now1;
    if (m1.top().first < now1) m1.push(make_pair(now1, i + 1));
  }
  return true;
}
int main() {
  cin >> S;
  bool ok1 = false;
  for (int tm = 0; tm < 2; tm++) {
    bool now = true;
    for (int i = 0; i < S.size(); i++) {
      if (S[i] != '?' && S[i] - '0' != (tm + i) % 2) {
        now = false;
        break;
      }
    }
    if (now) {
      ok1 = true;
      break;
    }
  }
  if (ok1) {
    cout << 1 << endl;
    return 0;
  }
  int L = 1, R = S.size();
  while (R - L > 1) {
    int mid = L + R >> 1;
    if (check(mid))
      R = mid;
    else
      L = mid;
  }
  cout << R << endl;
}
