#include <bits/stdc++.h>
using namespace std;
struct BIT {
  int size;
  vector<long long> bit;
  BIT() { size = 0; }
  BIT(int s) {
    size = s;
    bit.resize(size + 1);
    init();
  }
  void init() {
    for (int i = 1; i <= size; i++) bit[i] = 0;
  }
  long long query(int i) {
    long long ret = 0;
    while (i > 0) {
      ret += bit[i];
      i -= i & (-i);
    }
    return ret;
  }
  void add(int i, long long x) {
    while (i <= size) {
      bit[i] += x;
      i += i & (-i);
    }
  }
};
string s;
BIT bit(1000005);
void update(long long p, long long x) {
  long long v = bit.query(p), d = x - v;
  bit.add(p, d), bit.add(p + 1, -d);
}
long long get(long long l, long long r) {
  long long ub = r + 1, lb = l - 1, mid;
  while (ub - lb > 1) {
    mid = (ub + lb) / 2;
    long long res = bit.query(mid);
    if (res > 0) {
      if (res > 1e18 / 2) {
        if (bit.query(mid + 1) > 0 || bit.query(mid - 1) > 0)
          lb = mid;
        else
          ub = mid;
      } else
        lb = mid;
    } else
      ub = mid;
  }
  return lb;
}
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> s;
  long long n = s.size();
  s = "#" + s;
  bit.add(1, 1e18);
  update(1000002, 0);
  long long l = 1000002, r = 1000002, k = 1000002;
  for (int i = 1; i <= n; i++) {
    if (s[i] == '0') {
      long long res = get(l, r);
      if (res >= l) bit.add(l, -1), bit.add(res + 1, 1);
      l--;
      update(l, 1e18);
    }
    if (s[i] == '1') {
      bit.add(l, 1), bit.add(r + 1, -1);
      l++;
      long long x = min(bit.query(l - 1), bit.query(l));
      update(l, x);
      update(l - 1, 1e18);
    }
    if (s[i] == '?') {
      if (l == k) {
        long long x = min(bit.query(k), bit.query(k + 1)) + 1;
        long long res = get(l, r);
        if (res >= l) bit.add(l, -1), bit.add(res + 1, 1);
        l--;
        k--;
        update(k, x);
      } else {
        long long x = bit.query(k + 1) + 1, y = bit.query(k) + 1;
        long long res = get(l, r);
        if (res >= l) bit.add(l, -1), bit.add(res + 1, 1);
        l--;
        k -= 2;
        update(k, y), update(k + 1, x);
      }
    }
    k = max(l, k);
  }
  long long ans = 1e18;
  for (int i = l; i <= r; i++) {
    ans = min(ans, bit.query(i) + (i - l));
  }
  cout << ans << endl;
  return 0;
}
