#include <algorithm>
#include <cassert>
#include <cstring>
#include <iostream>
#include <vector>

#define TRACE(x) std::cout << #x << " = " << x << "\n"
#define _ << " _ " <<

using namespace std;

const int MAX = 1001000;

int fl[MAX][2], fr[MAX][2];

int main() {
  std::ios_base::sync_with_stdio(false);

  string S;
  cin >> S;

  int N = S.size();
  auto can = [&](int K) -> bool {
    for (int i = 0; i <= N; ++i) {
      for (int j = 0; j < 2; ++j) {
        fl[i][j] = MAX, fr[i][j] = -MAX;
      }
    }

    fl[0][0] = 0, fr[0][0] = K - (K % 2 ? 1 : 0);
    fl[0][1] = 1, fr[0][1] = K - (K % 2 ? 0 : 1);
    for (int i = 0; i <= N; ++i) {
      for (int j = 0; j < 2; ++j) {
        fl[i][j] = max(fl[i][j], fl[0][j]);
        fr[i][j] = min(fr[i][j], fr[0][j]);
        if (fl[i][j] > fr[i][j]) fl[i][j] = MAX, fr[i][j] = -MAX;
      }
      if (i == N) break;
      if (S[i] == '0') {
        for (int j = 0; j < 2; ++j) {
          fl[i + 1][j ^ 1] = fl[i][j] - 1;
          fr[i + 1][j ^ 1] = fr[i][j] - 1;
        }
      } else if (S[i] == '1') {
        for (int j = 0; j < 2; ++j) {
          fl[i + 1][j ^ 1] = fl[i][j] + 1;
          fr[i + 1][j ^ 1] = fr[i][j] + 1;
        }
      } else {
        for (int j = 0; j < 2; ++j) {
          fl[i + 1][j ^ 1] = fl[i][j] - 1;
          fr[i + 1][j ^ 1] = fr[i][j] + 1;
        }
      }
    }

    return fl[N][0] <= fr[N][0] || fl[N][1] <= fr[N][1];
  };

  int lo = 0, hi = N;
  while (lo < hi) {
    int mid = (lo + hi) / 2;
    if (can(mid))
      hi = mid;
    else
      lo = mid + 1;
  }

  cout << lo << '\n';
  return 0;
}
