#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
using namespace std;
long long MOD = 1e9 + 7;
double eps = 1e-12;
long long mpow(long long a, long long b) {
  if (a == 0) return 0;
  if (b == 0) return 1;
  long long t1 = mpow(a, b / 2);
  t1 *= t1;
  t1 %= MOD;
  if (b % 2) t1 *= a;
  t1 %= MOD;
  return t1;
}
long long mpow(long long a, long long b, long long p) {
  if (a == 0) return 0;
  if (b == 0) return 1;
  long long t1 = mpow(a, b / 2, p);
  t1 *= t1;
  t1 %= p;
  if (b % 2) t1 *= a;
  t1 %= p;
  return t1;
}
long long modinverse(long long a, long long m) {
  long long m0 = m;
  long long y = 0, x = 1;
  if (m == 1) return 0;
  while (a > 1) {
    long long q = a / m;
    long long t = m;
    m = a % m, a = t;
    t = y;
    y = x - q * y;
    x = t;
  }
  if (x < 0) x += m0;
  return x;
}
mt19937_64 mt(chrono::steady_clock::now().time_since_epoch().count());
long long range(long long l, long long r) { return l + mt() % (r - l + 1); }
long long rev(long long v) { return mpow(v, MOD - 2); }
long long n;
vector<long long> a;
string s;
bool check_interval(long long l, long long r) {
  long long st = 0, en = 0;
  for (long long i = 0; i < n; i++) {
    if (s[i] == '?') {
      en += 2;
    }
    long long curl = l + a[i], curr = r + a[i];
    if (curl % 2) curl++;
    if (curr % 2) curr--;
    if (en < curl)
      return -1;
    else if (curr < st)
      return 1;
    st = max(st, curl);
    en = min(en, curr);
  }
  return 0;
}
bool check(long long len) {
  long long l = 0, r = len;
  while (l != r) {
    long long high = (l + r) / 2;
    long long v = check_interval(high - len, high);
    if (v == 0)
      return 1;
    else if (v == -1) {
      r = high - 1;
    } else {
      l = high + 1;
    }
  }
  long long v = check_interval(l - len, l);
  if (v == 0) return 1;
  return 0;
}
void solve() {
  cin >> s;
  n = ((long long)(s).size());
  long long v[n], sum[n];
  for (long long i = 0; i < n; i++) {
    if (s[i] == '1') {
      v[i] = (i ? v[i - 1] : 0) + 1;
      sum[i] = (i ? sum[i - 1] : 0);
    } else if (s[i] == '0') {
      v[i] = (i ? v[i - 1] : 0) - 1;
      sum[i] = (i ? sum[i - 1] : 0);
    } else {
      v[i] = (i ? v[i - 1] : 0);
      sum[i] = (i ? sum[i - 1] : 0) + 1;
    }
  }
  a.resize(n);
  for (long long i = 0; i < n; i++) a[i] = sum[i] - v[i];
  long long l = 0, r = n;
  while (l != r) {
    long long len = (l + r) / 2;
    if (check(len))
      r = len;
    else
      l = len + 1;
  }
  cout << l << "\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  long long t = 1;
  for (long long i = 0; i < t; i++) {
    solve();
  }
  return 0;
}
