#include <bits/stdc++.h>
using namespace std;
double getTime() {
  struct timeval tv;
  gettimeofday(&tv, NULL);
  return tv.tv_sec + tv.tv_usec / 1e6;
}
const int MX = 1000001;
int val[MX], quest[MX], rev[MX];
namespace seg_tree {
const int SIZE = 2 * MX;
struct {
  int l, r;
  int lSon, rSon;
  int mn, mx, quest, rev, add;
} t[SIZE];
void recalc(int v) {
  t[v].mn = t[v].add + min(t[t[v].lSon].mn, t[t[v].rSon].mn);
  t[v].mx = t[v].add + max(t[t[v].lSon].mx, t[t[v].rSon].mx);
  t[v].quest = t[t[v].lSon].quest + t[t[v].rSon].quest;
  t[v].rev = t[t[v].lSon].rev + t[t[v].rSon].rev;
}
int tw = 0;
int build(int l, int r) {
  int v = ++tw;
  assert(v < SIZE);
  t[v].l = l;
  t[v].r = r;
  t[v].add = 0;
  if (l < r) {
    t[v].lSon = build(l, (l + r) / 2);
    t[v].rSon = build((l + r) / 2 + 1, r);
    recalc(v);
  } else {
    t[v].mn = t[v].mx = val[l];
    t[v].quest = quest[l];
    t[v].rev = rev[l];
  }
  return v;
}
void flipKthQuest(int v, int k) {
  if (t[v].l == t[v].r) {
    t[v].mn += 2;
    t[v].mx += 2;
    assert(t[v].quest == 1 && k == 1);
    t[v].quest = 0;
    t[v].rev = 1;
    return;
  }
  if (t[t[v].lSon].quest >= k) {
    flipKthQuest(t[v].lSon, k);
    t[t[v].rSon].mn += 2;
    t[t[v].rSon].mx += 2;
    t[t[v].rSon].add += 2;
  } else {
    flipKthQuest(t[v].rSon, k - t[t[v].lSon].quest);
  }
  recalc(v);
}
void flipKthRev(int v, int k) {
  if (t[v].l == t[v].r) {
    t[v].mn -= 2;
    t[v].mx -= 2;
    assert(t[v].rev == 1 && k == 1);
    t[v].quest = 1;
    t[v].rev = 0;
    return;
  }
  if (t[t[v].lSon].rev >= k) {
    flipKthRev(t[v].lSon, k);
    t[t[v].rSon].mn -= 2;
    t[t[v].rSon].mx -= 2;
    t[t[v].rSon].add -= 2;
  } else {
    flipKthRev(t[v].rSon, k - t[t[v].lSon].rev);
  }
  recalc(v);
}
pair<int, int> countBeforeMin(int v) {
  if (t[v].l == t[v].r) return {t[v].quest, t[v].rev};
  if (t[t[v].lSon].mn + t[v].add == t[v].mn) {
    return countBeforeMin(t[v].lSon);
  } else {
    assert(t[t[v].rSon].mn + t[v].add == t[v].mn);
    auto res = countBeforeMin(t[v].rSon);
    res.first += t[t[v].lSon].quest;
    res.second += t[t[v].lSon].rev;
    return res;
  }
}
}  // namespace seg_tree
char s[MX + 1];
int suffmin[MX + 1], x[MX];
int main() {
  double startTime = getTime();
  ignore = scanf("%s", s);
  int n = strlen(s);
  suffmin[n] = 0;
  for (int i = n - 1; i >= 0; i--) {
    if (s[i] == '0')
      suffmin[i] = suffmin[i + 1] - 1;
    else
      suffmin[i] = min(0, suffmin[i + 1] + 1);
  }
  int mn = suffmin[0];
  for (int i = 0, cur = 0; i < n; i++) {
    if (s[i] == '?') {
      if (cur - 1 + suffmin[i + 1] >= mn) {
        x[i] = -1;
      } else {
        x[i] = 1;
      }
    } else {
      x[i] = s[i] == '0' ? -1 : 1;
    }
    cur += x[i];
  }
  val[0] = 0;
  for (int i = 0; i < n; i++) {
    val[i + 1] = val[i] + x[i];
    if (s[i] == '?') {
      if (x[i] == -1)
        quest[i + 1] = 1;
      else
        rev[i + 1] = 1;
    }
  }
  int root = seg_tree::build(0, n);
  int ans = seg_tree::t[root].mx - seg_tree::t[root].mn;
  int it = 0;
  while (true) {
    int q, r;
    tie(q, r) = seg_tree::countBeforeMin(root);
    if (q == 0) break;
    if (r < seg_tree::t[root].rev) {
      seg_tree::flipKthRev(root, r + 1);
    }
    seg_tree::flipKthQuest(root, q);
    ans = min(seg_tree::t[root].mx - seg_tree::t[root].mn, ans);
    it++;
    if (it == 1000) {
      it = 0;
      if (getTime() - startTime > 1.9) break;
    }
  }
  printf("%d\n", ans);
  return 0;
}
