#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
char s[maxn];
int n, mid, Min[maxn << 2], Max[maxn << 2], Add[maxn << 2], sum[maxn];
void pushup(int rt) {
  Min[rt] = min(Min[(rt << 1)], Min[(rt << 1 | 1)]);
  Max[rt] = max(Max[(rt << 1)], Max[(rt << 1 | 1)]);
}
void lazy(int rt, int x) {
  Min[rt] += x;
  Max[rt] += x;
  Add[rt] += x;
}
void pushdown(int rt) {
  if (Add[rt]) {
    lazy((rt << 1), Add[rt]);
    lazy((rt << 1 | 1), Add[rt]);
    Add[rt] = 0;
  }
}
void build(int rt, int l, int r) {
  Add[rt] = 0;
  if (l == r) {
    Min[rt] = Max[rt] = 2 * sum[l] - l;
    return;
  }
  int mid = l + r >> 1;
  build((rt << 1), l, mid);
  build((rt << 1 | 1), mid + 1, r);
  pushup(rt);
}
void update(int rt, int l, int r, int a, int b) {
  if (a <= l && r <= b) {
    lazy(rt, 2);
    return;
  }
  pushdown(rt);
  int mid = l + r >> 1;
  if (a <= mid) update((rt << 1), l, mid, a, b);
  if (b > mid) update((rt << 1 | 1), mid + 1, r, a, b);
  pushup(rt);
}
int queryMin(int rt, int l, int r, int a, int b) {
  if (a <= l && r <= b) return Min[rt];
  pushdown(rt);
  int mid = l + r >> 1;
  if (b <= mid)
    return queryMin((rt << 1), l, mid, a, b);
  else if (a > mid)
    return queryMin((rt << 1 | 1), mid + 1, r, a, b);
  else
    return min(queryMin((rt << 1), l, mid, a, b),
               queryMin((rt << 1 | 1), mid + 1, r, a, b));
}
int queryMax(int rt, int l, int r, int a, int b) {
  if (a <= l && r <= b) return Max[rt];
  pushdown(rt);
  int mid = l + r >> 1;
  if (b <= mid)
    return queryMax((rt << 1), l, mid, a, b);
  else if (a > mid)
    return queryMax((rt << 1 | 1), mid + 1, r, a, b);
  else
    return max(queryMax((rt << 1), l, mid, a, b),
               queryMax((rt << 1 | 1), mid + 1, r, a, b));
}
bool check() {
  build(1, 0, n);
  stack<int> sta;
  for (int i = 1; i <= n; ++i) {
    if (s[i] == '?') sta.push(i);
    if (queryMax(1, 0, n, 0, i - 1) - mid > queryMax(1, 0, n, i, i)) {
      if (sta.empty()) return 0;
      int pos = sta.top();
      sta.pop();
      update(1, 0, n, pos, n);
    }
    if (queryMin(1, 0, n, 0, i) + mid < queryMax(1, 0, n, 0, i)) return 0;
  }
  return 1;
}
int main() {
  scanf("%s", s + 1);
  n = strlen(s + 1);
  for (int i = 1; i <= n; ++i) sum[i] = sum[i - 1] + (s[i] == '1');
  int l = 1, r = n;
  while (l <= r) {
    mid = l + r >> 1;
    if (check())
      r = mid - 1;
    else
      l = mid + 1;
  }
  printf("%d\n", l);
  return 0;
}
