#include <bits/stdc++.h>
using namespace std;
template <typename T>
struct lazysegtree {
  using F = function<T(T, T)>;
  using G = function<T(T, T, int, int)>;
  const F calcfn, lazycalcfn;
  const G updatefn;
  int n;
  T defvalue, lazydefvalue;
  vector<T> dat, lazy;
  vector<bool> lazyflag;
  lazysegtree(
      int n_ = 0, T defvalue_ = 0,
      const F calcfn_ = [](T a, T b) { return a + b; },
      const F lazycalcfn_ = [](T a, T b) { return a + b; },
      const G updatefn_ = [](T a, T b, int l,
                             int r) { return a + b * (r - l); },
      T lazydefvalue_ = 0)
      : defvalue(defvalue_),
        lazydefvalue(lazydefvalue_),
        calcfn(calcfn_),
        lazycalcfn(lazycalcfn_),
        updatefn(updatefn_) {
    n = 1;
    while (n < n_) n <<= 1;
    dat.assign(2 * n - 1, defvalue);
    lazy.assign(2 * n - 1, lazydefvalue);
    lazyflag.assign(2 * n - 1, false);
  }
  void copy(const vector<T>& v) {
    for (int i = 0; i < v.size(); i++) dat[i + n - 1] = v[i];
    for (int i = n - 2; i >= 0; i--)
      dat[i] = calcfn(dat[2 * i + 1], dat[2 * i + 2]);
  }
  void eval(int i, int l, int r) {
    if (lazyflag[i]) {
      dat[i] = updatefn(dat[i], lazy[i], l, r);
      if (r - l > 1) {
        lazy[2 * i + 1] = lazycalcfn(lazy[2 * i + 1], lazy[i]);
        lazy[2 * i + 2] = lazycalcfn(lazy[2 * i + 2], lazy[i]);
        lazyflag[2 * i + 1] = lazyflag[2 * i + 2] = true;
      }
      lazy[i] = lazydefvalue;
      lazyflag[i] = false;
    }
  }
  void update(int a, int b, T x, int k = 0, int l = 0, int r = -1) {
    if (r < 0) r = n;
    eval(k, l, r);
    if (b <= l || r <= a)
      return;
    else if (a <= l && r <= b) {
      lazy[k] = lazycalcfn(lazy[k], x);
      lazyflag[k] = true;
      eval(k, l, r);
    } 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] = calcfn(dat[2 * k + 1], dat[2 * k + 2]);
    }
  }
  T query(int a, int b, int k = 0, int l = 0, int r = -1) {
    if (r < 0) r = n;
    eval(k, l, r);
    if (b <= l || r <= a)
      return defvalue;
    else if (a <= l && r <= b)
      return dat[k];
    else
      return calcfn(query(a, b, 2 * k + 1, l, (l + r) / 2),
                    query(a, b, 2 * k + 2, (l + r) / 2, r));
  }
};
string S;
bool check(int lim) {
  int now1 = 0, now0 = 0;
  stack<int> Q;
  vector<int> A0(S.size() + 1), A1(S.size() + 1);
  lazysegtree<pair<int, int> > P(
      S.size() + 1, make_pair(-1e7, 1e7),
      [](pair<int, int> a, pair<int, int> b) {
        return make_pair(max(a.first, b.first), min(a.second, b.second));
      },
      [](pair<int, int> a, pair<int, int> b) {
        return make_pair(a.first + b.first, 0);
      },
      [](pair<int, int> a, pair<int, int> b, int l, int r) {
        return make_pair(a.first + b.first, a.second + b.first);
      },
      make_pair(0, 0));
  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--;
      P.update(i + 1, S.size() + 1, make_pair(-1, 0));
    } else if (S[i] == '1') {
      now1++;
      now0++;
      P.update(i + 1, S.size() + 1, make_pair(1, 0));
    } 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;
        while (!Q.empty() && Q.top() > id) {
          int j = Q.top();
          Q.pop();
          P.update(j, S.size() + 1, make_pair(1, 0));
          now0 += 2;
        }
        while (m0.top().second > id) m0.pop();
        int X = A0[id] + P.query(id, i + 2).second - P.query(id, id + 1).second;
        if (m0.top().first > X) m0.push(make_pair(X, id));
        f1 = false;
        f2 = true;
      } else {
        int id = m0.top().second;
        while (!Q.empty() && Q.top() > id) {
          int j = Q.top();
          Q.pop();
          P.update(j, S.size() + 1, make_pair(-1, 0));
          now1 -= 2;
        }
        while (m1.top().second > id) m1.pop();
        int X = A1[id] + P.query(id, i + 2).first - P.query(id, id + 1).first;
        if (m1.top().first < X) m1.push(make_pair(X, id));
        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;
  int L = 0, R = S.size();
  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) L = 1;
  while (R - L > 1) {
    int mid = L + R >> 1;
    if (check(mid))
      R = mid;
    else
      L = mid;
  }
  cout << R << endl;
}
