#include <bits/stdc++.h>
namespace IO {
char gc() { return getchar(); }
template <typename Tp>
bool get1(Tp &x) {
  bool neg = 0;
  char c = gc();
  while (c != EOF && (c < '0' || c > '9') && c != '-') c = gc();
  if (c == '-') c = gc(), neg = 1;
  if (c == EOF) return false;
  x = 0;
  for (; c >= '0' && c <= '9'; c = gc()) x = x * 10 + c - '0';
  if (neg) x = -x;
  return true;
}
template <typename Tp>
void printendl(Tp x) {
  if (x < 0) putchar('-'), x = -x;
  static short a[40], sz;
  sz = 0;
  while (x > 0) a[sz++] = x % 10, x /= 10;
  if (sz == 0) putchar('0');
  for (int i = sz - 1; i >= 0; i--) putchar('0' + a[i]);
  puts("");
}
}  // namespace IO
using IO::get1;
using IO::printendl;
const int inf = 0x3f3f3f3f;
const long long Linf = 1ll << 61;
const int maxn = 1000111;
namespace sgt {
int dlt[2100111], mn[2100111], mx[2100111];
void add(int t, int v) {
  mn[t] += v;
  mx[t] += v;
  dlt[t] += v;
}
void push(int t) {
  if (dlt[t]) {
    add((t << 1), dlt[t]);
    add(((t << 1) | 1), dlt[t]);
    dlt[t] = 0;
  }
}
void modify(int l, int r, int v, int tl, int tr, int t) {
  if (l <= tl && tr <= r) {
    add(t, v);
    return;
  }
  push(t);
  int mid = (tl + tr) / 2;
  if (l <= mid) modify(l, r, v, tl, mid, (t << 1));
  if (r > mid) modify(l, r, v, mid + 1, tr, ((t << 1) | 1));
  mn[t] = std::min(mn[(t << 1)], mn[((t << 1) | 1)]);
  mx[t] = std::max(mx[(t << 1)], mx[((t << 1) | 1)]);
}
int qmin(int l, int r, int tl, int tr, int t) {
  if (l <= tl && tr <= r) return mn[t];
  push(t);
  int mid = (tl + tr) / 2, ret = inf;
  if (l <= mid) ret = std::min(ret, qmin(l, r, tl, mid, (t << 1)));
  if (r > mid) ret = std::min(ret, qmin(l, r, mid + 1, tr, ((t << 1) | 1)));
  return ret;
}
int qmax(int l, int r, int tl, int tr, int t) {
  if (l <= tl && tr <= r) return mx[t];
  push(t);
  int mid = (tl + tr) / 2, ret = -inf;
  if (l <= mid) ret = std::max(ret, qmax(l, r, tl, mid, (t << 1)));
  if (r > mid) ret = std::max(ret, qmax(l, r, mid + 1, tr, ((t << 1) | 1)));
  return ret;
}
int qfirst(int v, int tl, int tr, int t) {
  if (mn[t] > v) return tr + 1;
  if (tl == tr) return tl;
  push(t);
  int mid = (tl + tr) / 2;
  if (mn[(t << 1)] == v)
    return qfirst(v, tl, mid, (t << 1));
  else
    return qfirst(v, mid + 1, tr, ((t << 1) | 1));
}
};  // namespace sgt
char s[maxn];
int n;
int main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  std::set<int> S0, S1;
  for (int i = 1; i <= n; i++) {
    if (s[i] == '0')
      sgt::modify(i, n, 1, 0, n, 1);
    else if (s[i] == '1')
      sgt::modify(i, n, -1, 0, n, 1);
    else {
      sgt::modify(i, n, -1, 0, n, 1);
      S1.insert(i);
    }
  }
  int mnv = sgt::qmin(1, n, 0, n, 1), ans = sgt::qmax(1, n, 0, n, 1) - mnv;
  while (true) {
    while (sgt::qmin(1, n, 0, n, 1) == mnv) {
      int pos = sgt::qfirst(mnv, 0, n, 1);
      auto it = S1.upper_bound(pos);
      if (it != S1.begin()) {
        it--;
        int v = *it;
        S0.insert(v);
        S1.erase(v);
        sgt::modify(v, n, 2, 0, n, 1);
        it = S0.lower_bound(pos + 1);
        if (it != S0.end()) {
          int v = *it;
          S1.insert(v);
          S0.erase(v);
          sgt::modify(v, n, -2, 0, n, 1);
        }
      } else {
        break;
      }
    }
    if (sgt::qmin(1, n, 0, n, 1) == mnv) break;
    mnv = sgt::qmin(1, n, 0, n, 1);
    ans = std::min(ans, sgt::qmax(1, n, 0, n, 1) - mnv);
  }
  printendl(ans);
  return 0;
}
