#include <bits/stdc++.h>
using namespace std;
const int maxn = 1 << 20;
struct T {
  int sum, pre;
  T() : sum(0), pre(0) {}
  T(int sum, int pre) : sum(sum), pre(pre) {}
  inline T operator+(const T &rhs) const {
    return T(sum + rhs.sum, min(pre, sum + rhs.pre));
  }
} t[maxn << 1];
void clr() {
  for (int i = 0; i < (int)(maxn << 1); ++i) t[i] = T();
}
inline void upd(int x, int v) {
  t[x += maxn] = T(v, min(v, 0));
  while (x >>= 1) t[x] = t[x << 1] + t[x << 1 | 1];
}
int n;
char s[maxn];
int stk[maxn];
int ans[maxn];
bool chk(int lim) {
  int top = 0;
  int nw_diff = 0;
  clr();
  for (int i = 0; i < (int)(n); ++i) {
    char c = s[i] == '?' ? '0' : s[i];
    if (s[i] == '?') stk[top++] = i;
    int x = c == '0' ? 1 : -1;
    upd(i, x);
    ans[i] = x;
    nw_diff += x;
    while (nw_diff - t[1].pre > lim) {
      if (not top) return 0;
      --top;
      ans[stk[top]] = -1;
      upd(stk[top], -1);
      nw_diff -= 2;
    }
  }
  {
    int nw_diff = 0, mn_diff = 0;
    for (int i = 0; i < (int)(n); ++i) {
      int x = ans[i];
      nw_diff -= x;
      mn_diff = min(nw_diff, mn_diff);
      if (nw_diff - mn_diff > lim) return 0;
    }
  }
  return 1;
}
int main() {
  scanf("%s", s);
  n = strlen(s);
  int lb = 1, rb = n;
  while (lb < rb) {
    int md = (lb + rb) >> 1;
    if (chk(md))
      rb = md;
    else
      lb = md + 1;
  }
  printf("%d\n", lb);
  return 0;
}
