#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 10;
char s[maxn];
int n, mid, sum[maxn], b[maxn];
bool check() {
  stack<int> sta;
  int Max = 0, Min = 0, Maxpos = 0, flag = 1, delta = 0, cur = 0;
  for (int i = 1; i <= n; ++i) {
    b[i] = (s[i] == '1' ? 1 : 0);
    cur = cur + 2 * b[i] - 1;
    if (s[i] == '?') sta.push(i);
    if (Max - mid > cur + delta) {
      if (sta.empty()) return 0;
      int pos = sta.top();
      sta.pop();
      if (pos == Maxpos + 1 && flag) {
        flag = 0;
        ++Max;
        Maxpos = pos;
      }
      delta += 2;
      b[pos] = 1;
    }
    if (Max <= cur + delta) {
      Max = cur + delta;
      Maxpos = i;
    }
  }
  Max = Min = 0;
  for (int i = 1; i <= n; ++i) {
    b[i] += b[i - 1];
    Max = max(Max, 2 * b[i] - i);
    Min = min(Min, 2 * b[i] - i);
    if (Max - Min > mid) 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;
}
