#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
char s[N];
int n;
set<int> st;
set<int> st2;
int mx[N << 2], mn[N << 2], tg[N << 2];
inline void psh(int x, int s) {
  tg[x] += s;
  mx[x] += s, mn[x] += s;
}
inline void pd(int x, int l, int r) {
  if (tg[x]) {
    if (l ^ r) psh(x << 1, tg[x]), psh(x << 1 | 1, tg[x]);
    tg[x] = 0;
  }
}
inline void add(int x, int l, int r, int ql, int qr, int s) {
  pd(x, l, r);
  if (ql <= l && qr >= r) {
    psh(x, s);
    return;
  }
  int mid = (l + r) >> 1;
  if (ql <= mid) add(x << 1, l, mid, ql, qr, s);
  if (qr > mid) add(x << 1 | 1, mid + 1, r, ql, qr, s);
  mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
  mn[x] = min(mn[x << 1], mn[x << 1 | 1]);
}
inline int find(int x, int l, int r) {
  pd(x, l, r);
  if (l == r) return l;
  int mid = (l + r) >> 1;
  if (mx[x << 1] == mx[x])
    return find(x << 1, l, mid);
  else
    return find(x << 1 | 1, mid + 1, r);
}
inline int findr(int x, int l, int r) {
  pd(x, l, r);
  if (l == r) return l;
  int mid = (l + r) >> 1;
  if (mx[x << 1 | 1] != mx[x])
    return findr(x << 1, l, mid);
  else
    return findr(x << 1 | 1, mid + 1, r);
}
inline int qmax(int x, int l, int r, int ql, int qr) {
  pd(x, l, r);
  if (ql <= l && qr >= r) return mx[x];
  int ans = -0x3f3f3f3f, mid = (l + r) >> 1;
  if (ql <= mid) ans = max(qmax(x << 1, l, mid, ql, qr), ans);
  if (qr > mid) ans = max(qmax(x << 1 | 1, mid + 1, r, ql, qr), ans);
  return ans;
}
int main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  for (int i = 1; i <= n; i++) {
    if (s[i] == '0') {
      add(1, 0, n, i, n, -1);
    } else {
      add(1, 0, n, i, n, 1);
      if (s[i] == '?') st.insert(i);
    }
  }
  int ans = 0x3f3f3f3f;
  while (1) {
    int mxp = find(1, 0, n);
    int cMx = mx[1];
    ans = min(ans, mx[1] - mn[1]);
    set<int>::iterator q = st.upper_bound(mxp);
    if (q == st.begin()) break;
    --q;
    int Mx = qmax(1, 0, n, 0, mxp - 1);
    if (Mx > cMx - 2) {
      set<int>::iterator q2 = st2.upper_bound(findr(1, 0, n));
      if (q2 != st2.end()) {
        add(1, 0, n, *q2, n, 2);
        st2.erase(q2);
      }
    }
    add(1, 0, n, *q, n, -2);
    st2.insert(*q);
    st.erase(q);
  }
  for (int i = 1; i < N << 2; i++) mx[i] = mn[i] = tg[i] = 0;
  st.clear(), st2.clear();
  for (int i = 1; i <= n; i++) {
    if (s[i] == '1') {
      add(1, 0, n, i, n, -1);
    } else {
      add(1, 0, n, i, n, 1);
      if (s[i] == '?') st.insert(i);
    }
  }
  while (1) {
    int mxp = find(1, 0, n);
    int cMx = mx[1];
    ans = min(ans, mx[1] - mn[1]);
    set<int>::iterator q = st.upper_bound(mxp);
    if (q == st.begin()) break;
    --q;
    int Mx = qmax(1, 0, n, 0, mxp - 1);
    if (Mx > cMx - 2) {
      set<int>::iterator q2 = st2.upper_bound(findr(1, 0, n));
      if (q2 != st2.end()) {
        add(1, 0, n, *q2, n, 2);
        st2.erase(q2);
      }
    }
    add(1, 0, n, *q, n, -2);
    st2.insert(*q);
    st.erase(q);
  }
  reverse(s + 1, s + n + 1);
  for (int i = 1; i < N << 2; i++) mx[i] = mn[i] = tg[i] = 0;
  st.clear(), st2.clear();
  for (int i = 1; i <= n; i++) {
    if (s[i] == '0') {
      add(1, 0, n, i, n, -1);
    } else {
      add(1, 0, n, i, n, 1);
      if (s[i] == '?') st.insert(i);
    }
  }
  while (1) {
    int mxp = find(1, 0, n);
    int cMx = mx[1];
    ans = min(ans, mx[1] - mn[1]);
    set<int>::iterator q = st.upper_bound(mxp);
    if (q == st.begin()) break;
    --q;
    int Mx = qmax(1, 0, n, 0, mxp - 1);
    if (Mx > cMx - 2) {
      set<int>::iterator q2 = st2.upper_bound(findr(1, 0, n));
      if (q2 != st2.end()) {
        add(1, 0, n, *q2, n, 2);
        st2.erase(q2);
      }
    }
    add(1, 0, n, *q, n, -2);
    st2.insert(*q);
    st.erase(q);
  }
  printf("%d\n", ans);
  return 0;
}
