#include <bits/stdc++.h>
using namespace std;
inline long long read() {
  long long x = 0, f = 1;
  char c = getchar();
  while ((c < '0' || c > '9') && (c != '-')) c = getchar();
  if (c == '-') f = -1, c = getchar();
  while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
  return x * f;
}
const int N = 1e6 + 10;
int n, suf[N][2];
char s[N];
inline int calc10(int x) {
  if (suf[1][0] > x) return 1e9;
  int ret = 0, s = 0, mx = 0, s2 = 0, mx2 = 0;
  for (register int i = (1); i <= (n); i++) {
    if (::s[i] == '0') {
      s++, mx = max(mx, s);
      s2 = max(0, s2 - 1);
    } else if (::s[i] == '1') {
      s2++, mx2 = max(mx2, s2);
      s = max(0, s - 1);
    } else {
      if (s + 1 + suf[i + 1][0] > x) {
        s2++, mx2 = max(mx2, s2);
        s = max(0, s - 1);
      } else {
        s++, mx = max(mx, s);
        s2 = max(0, s2 - 1);
      }
    }
    if (s + suf[i + 1][0] > x) return 1e9;
  }
  return mx2;
}
inline int calc01(int x) {
  if (suf[1][1] > x) return 1e9;
  int s = 0, mx = 0, s2 = 0, mx2 = 0;
  for (register int i = (1); i <= (n); i++) {
    if (::s[i] == '1') {
      s++, mx = max(mx, s);
      s2 = max(0, s2 - 1);
    } else if (::s[i] == '0') {
      s2++, mx2 = max(mx2, s2);
      s = max(0, s - 1);
    } else {
      if (s + 1 + suf[i + 1][1] > x) {
        s2++, mx2 = max(mx2, s2);
        s = max(0, s - 1);
      } else {
        s++, mx = max(mx, s);
        s2 = max(0, s2 - 1);
      }
    }
    if (s + suf[i + 1][1] > x) return 1e9;
  }
  return mx2;
}
int main() {
  scanf("%s", s + 1), n = strlen(s + 1);
  for (register int i = (n); i >= (1); i--) {
    if (s[i] == '0') {
      suf[i][0] = suf[i + 1][0] + 1;
      suf[i][1] = max(0, suf[i + 1][1] - 1);
    } else if (s[i] == '1') {
      suf[i][0] = max(0, suf[i + 1][0] - 1);
      suf[i][1] = suf[i + 1][1] + 1;
    } else {
      suf[i][0] = max(0, suf[i + 1][0] - 1);
      suf[i][1] = max(0, suf[i + 1][1] - 1);
    }
  }
  int ans = n;
  int l = 0, r = n, ret = -1;
  while (l <= r) {
    int mid = l + r >> 1;
    if (calc10(mid) <= mid)
      ret = mid, r = mid - 1;
    else
      l = mid + 1;
  }
  if (ret != -1) {
    ans = min(ans, max(ret, calc10(ret)));
    if (ret != 0) ans = min(ans, max(ret - 1, calc10(ret - 1)));
  }
  l = 0, r = n, ret = -1;
  while (l <= r) {
    int mid = l + r >> 1;
    if (calc01(mid) <= mid)
      ret = mid, r = mid - 1;
    else
      l = mid + 1;
  }
  if (ret != -1) {
    ans = min(ans, max(ret, calc01(ret)));
    if (ret != 0) ans = min(ans, max(ret - 1, calc01(ret - 1)));
  }
  printf("%d\n", ans);
}
