#include <bits/stdc++.h>
using namespace std;
const int _ = 1e6 + 7;
char str[_];
int N, preval[_];
int ch[_ << 2], mx[_ << 2], id[_ << 2], mrk[_ << 2], mn[_ << 2], pid[_ << 2];
void mark(int x, int v) {
  mx[x] += v;
  mn[x] += v;
  mrk[x] += v;
}
void down(int x) {
  if (mrk[x]) {
    mark((x << 1), mrk[x]);
    mark((x << 1 | 1), mrk[x]);
    mrk[x] = 0;
  }
}
void up(int x) {
  mx[x] = max(mx[(x << 1)], mx[(x << 1 | 1)]);
  mn[x] = min(mn[(x << 1)], mn[(x << 1 | 1)]);
  id[x] = (mx[x] == mx[(x << 1)] ? id[(x << 1)] : id[(x << 1 | 1)]);
  pid[x] = min(pid[(x << 1)], pid[(x << 1 | 1)]);
}
void init(int x, int l, int r) {
  if (l == r) {
    mx[x] = mn[x] = preval[l];
    id[x] = l;
    pid[x] = 1e9;
    return;
  }
  init((x << 1), l, ((l + r) >> 1));
  init((x << 1 | 1), ((l + r) >> 1) + 1, r);
  up(x);
}
void setpid(int x, int l, int r, int tar, int flg) {
  if (l == r) {
    mark(x, flg ? -2 : 2);
    pid[x] = flg ? l : 1e9;
    return;
  }
  down(x);
  if (((l + r) >> 1) >= tar) {
    setpid((x << 1), l, ((l + r) >> 1), tar, flg);
    mark((x << 1 | 1), flg ? -2 : 2);
  } else
    setpid((x << 1 | 1), ((l + r) >> 1) + 1, r, tar, flg);
  up(x);
}
int qmin(int x, int l, int r, int val) {
  if (l == r) return l;
  down(x);
  return mx[(x << 1 | 1)] >= val
             ? qmin((x << 1 | 1), ((l + r) >> 1) + 1, r, val)
             : qmin((x << 1), l, ((l + r) >> 1), val);
}
int qsuf(int x, int l, int r, int L) {
  if (l >= L) return pid[x];
  int val = qsuf((x << 1 | 1), ((l + r) >> 1) + 1, r, L);
  if (((l + r) >> 1) >= L) val = min(val, qsuf((x << 1), l, ((l + r) >> 1), L));
  return val;
}
int brute(vector<pair<int, int> > value) {
  sort(value.begin(), value.end());
  int ans = 1e9;
  static int sufmn[1000003];
  for (int i = N; i; --i)
    sufmn[i] = max(sufmn[i + 1] + (str[i] == '1' ? 1 : -1), 0);
  for (int i = 0; i * N <= 1.5e8 && i < value.size(); ++i) {
    int cur = 0, mx = 0, mn = 0;
    for (int j = 1; j <= N; ++j) {
      if (str[j] != '?')
        cur += (str[j] == '1' ? 1 : -1);
      else
        cur += (cur + 1 + sufmn[j + 1] > value[i].second ? -1 : 1);
      mx = max(mx, cur);
      mn = min(mn, cur);
    }
    ans = min(ans, mx - mn);
  }
  return ans;
}
int main() {
  scanf("%s", str + 1);
  N = strlen(str + 1);
  for (int i = 1; i <= N; ++i)
    preval[i] = preval[i - 1] + (str[i] == '0' ? -1 : 1);
  init(1, 0, N);
  set<int> plc;
  int ans = 1e9;
  for (int i = 1; i <= N; ++i)
    if (str[i] == '?') plc.insert(i);
  vector<pair<int, int> > value;
  while (1) {
    value.push_back(make_pair(mx[1] - mn[1], mx[1]));
    ans = min(ans, mx[1] - mn[1]);
    int p = id[1];
    if (plc.upper_bound(p) == plc.begin()) break;
    int t = *--plc.upper_bound(p);
    if (p != N) {
      int t = qsuf(1, 0, N, p + 1);
      if (t <= N) {
        plc.insert(t);
        setpid(1, 0, N, t, 0);
      }
    }
    setpid(1, 0, N, t, 1);
    plc.erase(t);
  }
  cout << min(brute(value), ans);
  return 0;
}
