#include <bits/stdc++.h>
using namespace std;
const int inf = 2147483547;
int n;
char S[1000010];
int sum[1000010], at[1000010], cnt = 0;
int le[1000010], ri[1000010];
inline bool Judge(int mid) {
  le[0] = 0;
  ri[0] = mid;
  for (int i = 0; i <= cnt; ++i) {
    le[i] = -inf;
    ri[i] = inf;
  }
  for (int i = 0; i <= n; ++i) {
    le[at[i]] = max(le[at[i]], -sum[i]);
    ri[at[i]] = min(ri[at[i]], mid - sum[i]);
  }
  if (le[0] > ri[0]) return false;
  int l, r, ty;
  if (le[0] == ri[0]) {
    l = r = le[0];
    ty = (le[0] % 2);
  } else {
    l = le[0];
    r = ri[0];
    ty = 2;
  }
  for (int i = 1; i <= cnt; ++i) {
    if (ty == 2) {
      l--;
      r++;
      l = max(l, le[i]);
      r = min(r, ri[i]);
      if (l > r) return false;
      if (l == r) {
        ty = (l % 2);
        continue;
      }
      continue;
    }
    l--;
    r++;
    l = max(l, le[i]);
    r = min(r, ri[i]);
    if (l > r) return false;
    int g = (l % 2);
    ty ^= 1;
    if (l + (g ^ ty) > r) return false;
  }
  return true;
}
int main() {
  scanf("%s", S + 1);
  n = strlen(S + 1);
  cnt = 0;
  for (int i = 1; i <= n; ++i) {
    sum[i] += sum[i - 1];
    if (S[i] == '1') sum[i]++;
    if (S[i] == '0') sum[i]--;
    if (S[i] == '?') cnt++;
    at[i] = cnt;
  }
  int l = 0, r = n;
  while (l < r) {
    int mid = (l + r) >> 1;
    if (Judge(mid))
      r = mid;
    else
      l = mid + 1;
  }
  printf("%d\n", l);
  return 0;
}
