#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx")
#pragma GCC optimize("unroll-loops")
using namespace std;
template <typename T1, typename T2>
inline void chmin(T1& a, T2 b) {
  if (a > b) a = b;
}
template <typename T1, typename T2>
inline void chmax(T1& a, T2 b) {
  if (a < b) a = b;
}
std::random_device rd;
std::mt19937 mt(rd());
constexpr long long MOD = 1e9 + 7;
constexpr int MAX = 500050;
const long double pi = acos(-1);
constexpr long double EPS = 1e-10;
constexpr long long LINF = 1e18 + 1;
constexpr int INF = 1e9 + 1;
string S;
string T;
int dpr[2][1000010], dpl[2][1000010];
int N;
bool check(int x) {
  S = T;
  int ret1 = 0;
  for (int j = 0; j < (2); ++j) {
    for (int i = 0; i < (N + 2); ++i) {
      dpr[j][i] = 0;
      dpl[j][i] = 0;
    }
  }
  for (int i = N - 1; i >= 0; --i) {
    int res1 = dpr[1][i + 1] + ((S[i] == '1') ? 1 : -1);
    dpr[1][i] = max(0, res1);
    int res0 = dpr[0][i + 1] + ((S[i] == '0') ? 1 : -1);
    dpr[0][i] = max(0, res0);
    ret1 = max({ret1, res0, res1});
  }
  if (ret1 > x) return false;
  for (int i = 0; i < (N); ++i) {
    if (S[i] == '?') {
      int res0 = dpl[0][i] + dpr[0][i + 1];
      int res1 = dpl[1][i] + dpr[1][i + 1];
      if (res0 < res1)
        S[i] = '0';
      else
        S[i] = '1';
    }
    int res0 = dpl[0][i] + ((S[i] == '0') ? 1 : -1);
    int res1 = dpl[1][i] + ((S[i] == '1') ? 1 : -1);
    dpl[0][i + 1] = max(0, res0);
    dpl[1][i + 1] = max(0, res1);
    ret1 = max({ret1, res0, res1});
  }
  S = T;
  reverse(S.begin(), S.end());
  int ret2 = 0;
  for (int j = 0; j < (2); ++j) {
    for (int i = 0; i < (N + 2); ++i) {
      dpr[j][i] = 0;
      dpl[j][i] = 0;
    }
  }
  for (int i = N - 1; i >= 0; --i) {
    int res1 = dpr[1][i + 1] + ((S[i] == '1') ? 1 : -1);
    dpr[1][i] = max(0, res1);
    int res0 = dpr[0][i + 1] + ((S[i] == '0') ? 1 : -1);
    dpr[0][i] = max(0, res0);
    ret2 = max({ret2, res0, res1});
  }
  if (ret2 > x) return false;
  for (int i = 0; i < (N); ++i) {
    if (S[i] == '?') {
      int res0 = dpl[0][i] + dpr[0][i + 1];
      int res1 = dpl[1][i] + dpr[1][i + 1];
      if (res0 < res1)
        S[i] = '0';
      else
        S[i] = '1';
    }
    int res0 = dpl[0][i] + ((S[i] == '0') ? 1 : -1);
    int res1 = dpl[1][i] + ((S[i] == '1') ? 1 : -1);
    dpl[0][i + 1] = max(0, res0);
    dpl[1][i + 1] = max(0, res1);
    ret2 = max({ret2, res0, res1});
  }
  int ret = min(ret1, ret2);
  return ret <= x;
}
bool check2(int x) {
  S = T;
  int ret1 = 0;
  for (int j = 0; j < (2); ++j) {
    for (int i = 0; i < (N + 2); ++i) {
      dpr[j][i] = 0;
      dpl[j][i] = 0;
    }
  }
  for (int i = N - 1; i >= 0; --i) {
    int res1 = dpr[1][i + 1] + ((S[i] == '1') ? 1 : -1);
    dpr[1][i] = max(0, res1);
    int res0 = dpr[0][i + 1] + ((S[i] == '0') ? 1 : -1);
    dpr[0][i] = max(0, res0);
    ret1 = max({ret1, res0, res1});
  }
  if (ret1 > x) return false;
  for (int i = 0; i < (N); ++i) {
    if (S[i] == '?') {
      int res0 = dpl[0][i] + dpr[0][i + 1];
      int res1 = dpl[1][i] + dpr[1][i + 1];
      if (res0 > res1)
        S[i] = '0';
      else
        S[i] = '1';
    }
    int res0 = dpl[0][i] + ((S[i] == '0') ? 1 : -1);
    int res1 = dpl[1][i] + ((S[i] == '1') ? 1 : -1);
    dpl[0][i + 1] = max(0, res0);
    dpl[1][i + 1] = max(0, res1);
    ret1 = max({ret1, res0, res1});
  }
  S = T;
  reverse(S.begin(), S.end());
  int ret2 = 0;
  for (int j = 0; j < (2); ++j) {
    for (int i = 0; i < (N + 2); ++i) {
      dpr[j][i] = 0;
      dpl[j][i] = 0;
    }
  }
  for (int i = N - 1; i >= 0; --i) {
    int res1 = dpr[1][i + 1] + ((S[i] == '1') ? 1 : -1);
    dpr[1][i] = max(0, res1);
    int res0 = dpr[0][i + 1] + ((S[i] == '0') ? 1 : -1);
    dpr[0][i] = max(0, res0);
    ret2 = max({ret2, res0, res1});
  }
  if (ret2 > x) return false;
  for (int i = 0; i < (N); ++i) {
    if (S[i] == '?') {
      int res0 = dpl[0][i] + dpr[0][i + 1];
      int res1 = dpl[1][i] + dpr[1][i + 1];
      if (res0 > res1)
        S[i] = '0';
      else
        S[i] = '1';
    }
    int res0 = dpl[0][i] + ((S[i] == '0') ? 1 : -1);
    int res1 = dpl[1][i] + ((S[i] == '1') ? 1 : -1);
    dpl[0][i + 1] = max(0, res0);
    dpl[1][i + 1] = max(0, res1);
    ret2 = max({ret2, res0, res1});
  }
  int ret = min(ret1, ret2);
  return ret <= x;
}
bool check3(int x) {
  S = T;
  int ret1 = 0;
  for (int j = 0; j < (2); ++j) {
    for (int i = 0; i < (N + 2); ++i) {
      dpr[j][i] = 0;
      dpl[j][i] = 0;
    }
  }
  for (int i = N - 1; i >= 0; --i) {
    int res1 = dpr[1][i + 1] + ((S[i] == '1') ? 1 : -1);
    dpr[1][i] = max(0, res1);
    int res0 = dpr[0][i + 1] + ((S[i] == '0') ? 1 : -1);
    dpr[0][i] = max(0, res0);
    ret1 = max({ret1, res0, res1});
  }
  if (ret1 > x) return false;
  for (int i = 0; i < (N); ++i) {
    if (S[i] == '?') {
      int res0 = dpl[0][i] + dpr[0][i + 1];
      int res1 = dpl[1][i] + dpr[1][i + 1];
      if (res0 > res1)
        S[i] = '0';
      else if (res0 == res1) {
        if (mt() % 2 == 0)
          S[i] = '0';
        else
          S[i] = '1';
      } else
        S[i] = '1';
    }
    int res0 = dpl[0][i] + ((S[i] == '0') ? 1 : -1);
    int res1 = dpl[1][i] + ((S[i] == '1') ? 1 : -1);
    dpl[0][i + 1] = max(0, res0);
    dpl[1][i + 1] = max(0, res1);
    ret1 = max({ret1, res0, res1});
  }
  S = T;
  reverse(S.begin(), S.end());
  int ret2 = 0;
  for (int j = 0; j < (2); ++j) {
    for (int i = 0; i < (N + 2); ++i) {
      dpr[j][i] = 0;
      dpl[j][i] = 0;
    }
  }
  for (int i = N - 1; i >= 0; --i) {
    int res1 = dpr[1][i + 1] + ((S[i] == '1') ? 1 : -1);
    dpr[1][i] = max(0, res1);
    int res0 = dpr[0][i + 1] + ((S[i] == '0') ? 1 : -1);
    dpr[0][i] = max(0, res0);
    ret2 = max({ret2, res0, res1});
  }
  if (ret2 > x) return false;
  for (int i = 0; i < (N); ++i) {
    if (S[i] == '?') {
      int res0 = dpl[0][i] + dpr[0][i + 1];
      int res1 = dpl[1][i] + dpr[1][i + 1];
      if (res0 > res1)
        S[i] = '0';
      else if (res0 == res1) {
        if (mt() % 2 == 0)
          S[i] = '0';
        else
          S[i] = '1';
      } else
        S[i] = '1';
    }
    int res0 = dpl[0][i] + ((S[i] == '0') ? 1 : -1);
    int res1 = dpl[1][i] + ((S[i] == '1') ? 1 : -1);
    dpl[0][i + 1] = max(0, res0);
    dpl[1][i + 1] = max(0, res1);
    ret2 = max({ret2, res0, res1});
  }
  int ret = min(ret1, ret2);
  return ret <= x;
}
int calc(string S) {
  int N = S.size();
  int ans = 0;
  for (int l = 0; l < (N); ++l) {
    for (int r = l + 1; r < N + 1; ++r) {
      int c0 = 0, c1 = 0;
      for (int i = l; i < r; ++i) {
        if (S[i] == '0')
          c0++;
        else
          c1++;
      }
      chmax(ans, abs(c0 - c1));
    }
  }
  return ans;
}
int naive(string S) {
  int cnt = 0;
  int N = S.size();
  int mn = S.size();
  vector<int> pos;
  for (int i = 0; i < (N); ++i)
    if (S[i] == '?') {
      pos.push_back(i);
      cnt++;
    }
  for (int bit = 0; bit < (1 << cnt); ++bit) {
    string s = S;
    for (int i = 0; i < (cnt); ++i) {
      if (bit & (1 << i)) {
        s[pos[i]] = '1';
      } else
        s[pos[i]] = '0';
    }
    mn = min(mn, calc(s));
  }
  return mn;
}
int solve_(string s) {
  mt.seed((int)(time(0)));
  S = s;
  T = S;
  N = S.size();
  int ok = N, ng = 0;
  while (abs(ok - ng) > 1) {
    int mid = (ok + ng) / 2;
    if (check(mid) || check2(mid) || check3(mid) || check3(mid) ||
        check3(mid) || check3(mid) || check3(mid) || check3(mid))
      ok = mid;
    else
      ng = mid;
  }
  return ok;
}
bool test() {
  int n = mt() % 10 + 1;
  string s;
  for (int i = 0; i < (n); ++i) {
    int p = mt() % 3;
    if (p == 0)
      s += '0';
    else if (p == 1)
      s += '1';
    else
      s += '?';
  }
  cout << (s) << '\n';
  int ans_naive = naive(s);
  int ans_my = solve_(s);
  if (ans_naive != ans_my) {
    cout << "ans_naive"
         << ": " << ans_naive << endl;
    cout << "ans_my"
         << ": " << ans_my << endl;
    exit(0);
    return false;
  }
  cout << ("ok") << '\n';
  return true;
}
void solve() {
  mt.seed((int)(time(0)));
  cin >> S;
  if (S.size() <= 20) {
    cout << (naive(S)) << '\n';
    return;
  }
  T = S;
  N = S.size();
  int ok = N, ng = 0;
  while (abs(ok - ng) > 1) {
    int mid = (ok + ng) / 2;
    if (check(mid) || check2(mid) || check3(mid) || check3(mid) ||
        check3(mid) || check3(mid))
      ok = mid;
    else
      ng = mid;
  }
  cout << (ok) << '\n';
}
signed main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  solve();
}
