#include <bits/stdc++.h>
using namespace std;
string s;
int n, cum[1000005], a[1000005], f[2000005], lazy[4000005];
pair<pair<int, int>, pair<int, int> > tree[4000005];
pair<pair<int, int>, pair<int, int> > merge(
    pair<pair<int, int>, pair<int, int> > a,
    pair<pair<int, int>, pair<int, int> > b) {
  return {min(a.first, b.first), max(a.second, b.second)};
}
void build(int node, int st, int en) {
  if (st == en)
    tree[node] = {{a[st], st}, {a[st], st}};
  else {
    int mid = (st + en) / 2;
    build(2 * node, st, mid);
    build(2 * node + 1, mid + 1, en);
    tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
  }
}
void push(int node, int st, int en) {
  tree[node].first.first += lazy[node];
  tree[node].second.first += lazy[node];
  if (st != en) {
    lazy[2 * node] += lazy[node];
    lazy[2 * node + 1] += lazy[node];
  }
  lazy[node] = 0;
}
void update(int node, int st, int en, int l, int r) {
  if (l <= st && en <= r) lazy[node] += 2;
  push(node, st, en);
  if (en < l || st > r || r < l || (l <= st && en <= r)) return;
  int mid = (st + en) / 2;
  update(2 * node, st, mid, l, r);
  update(2 * node + 1, mid + 1, en, l, r);
  tree[node] = merge(tree[2 * node], tree[2 * node + 1]);
}
int solve(int l, int r) {
  int ans = 1e9, idx = 1e9;
  set<int> ind;
  for (int i = 0; i < n; i++) {
    if (s[i] == '?') ind.insert(i + 1);
  }
  build(1, 0, n);
  memset(lazy, 0, sizeof(lazy));
  for (int i = l; i <= r; i += 2) {
    idx = min(idx, f[i + n + 1]);
    idx = min(idx, f[i + n]);
    if (idx != 1e9) {
      auto it = ind.upper_bound(idx);
      if (it == ind.begin()) break;
      it = prev(it);
      update(1, 0, n, *it, n);
    }
    ans = min(ans, tree[1].second.first - i);
  }
  return ans;
}
int main() {
  cin >> s;
  n = s.size();
  for (int i = 0; i < n; i++) {
    cum[i + 1] = cum[i] + (s[i] == '1');
    a[i + 1] = 2 * cum[i + 1] - (i + 1);
  }
  for (int i = 0; i <= 2 * n + 2; i++) f[i] = 1e9;
  for (int i = 0; i <= n; i++) f[a[i] + n + 2] = min(f[a[i] + n + 2], i);
  printf("%d", min(solve(-n, n), solve(-n + 1, n)));
}
