#include <bits/stdc++.h>
using namespace std;
using ll = long long;
mt19937 rnd;
const ll N = 1 << 20;
const ll T = 2 * N;
const ll INF = 1e18;
struct info {
  ll minv = 0;
  ll mini = 0;
  ll maxv = 0;
  ll maxi = 0;
};
info neutral() {
  info v;
  v.minv = +INF;
  v.mini = -1;
  v.maxv = -INF;
  v.maxi = -1;
  return v;
}
info merge(info l, info r) {
  info v;
  if (l.minv <= r.minv) {
    v.minv = l.minv;
    v.mini = l.mini;
  } else {
    v.minv = r.minv;
    v.mini = r.mini;
  }
  if (l.maxv >= r.maxv) {
    v.maxv = l.maxv;
    v.maxi = l.maxi;
  } else {
    v.maxv = r.maxv;
    v.maxi = r.maxi;
  }
  return v;
}
info tval[T];
ll tadd[T];
ll ls(ll v) { return 2 * v + 1; }
ll rs(ll v) { return 2 * v + 2; }
void build(ll v, ll l, ll r) {
  tval[v].mini = l;
  tval[v].maxi = l;
  if (r - l > 1) {
    ll m = (l + r) / 2;
    build(ls(v), l, m);
    build(rs(v), m, r);
  }
}
void push(ll v) {
  ll l = ls(v);
  ll r = rs(v);
  tadd[l] += tadd[v];
  tval[l].minv += tadd[v];
  tval[l].maxv += tadd[v];
  tadd[r] += tadd[v];
  tval[r].minv += tadd[v];
  tval[r].maxv += tadd[v];
  tadd[v] = 0;
}
void upd(ll v, ll vl, ll vr, ll ql, ll qr, ll val) {
  if (ql <= vl && vr <= qr) {
    tadd[v] += val;
    tval[v].minv += val;
    tval[v].maxv += val;
    return;
  }
  if (qr <= vl || vr <= ql) {
    return;
  }
  push(v);
  ll vm = (vl + vr) / 2;
  upd(ls(v), vl, vm, ql, qr, val);
  upd(rs(v), vm, vr, ql, qr, val);
  tval[v] = merge(tval[ls(v)], tval[rs(v)]);
}
info query(ll v, ll vl, ll vr, ll ql, ll qr) {
  if (ql <= vl && vr <= qr) {
    return tval[v];
  }
  if (qr <= vl || vr <= ql) {
    return neutral();
  }
  push(v);
  ll vm = (vl + vr) / 2;
  return merge(query(ls(v), vl, vm, ql, qr), query(rs(v), vm, vr, ql, qr));
}
void upd(ll l, ll r, ll v) { upd(0, 0, N, l, r + 1, v); }
pair<ll, ll> qmax(ll l, ll r) {
  auto v = query(0, 0, N, l, r + 1);
  return {v.maxv, v.maxi};
}
pair<ll, ll> qmin(ll l, ll r) {
  auto v = query(0, 0, N, l, r + 1);
  return {v.minv, v.mini};
}
ll n;
string s;
ll a[N];
set<ll> neg;
set<ll> pos;
signed main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> s;
  n = (ll)s.size();
  build(0, 0, N);
  for (ll i = 0; i < n; ++i) {
    a[i] = (s[i] == '1' ? +1 : -1);
    if (s[i] == '?') {
      neg.insert(i);
    }
    upd(i + 1, n, a[i]);
  }
  ll answer = qmax(0, n).first - qmin(0, n).first;
  for (ll iter = 0; clock() < 1.9 * CLOCKS_PER_SEC; ++iter) {
    if ((iter / 8) % 2) {
      ll minv;
      ll mini;
      tie(minv, mini) = qmin(0, n);
      auto it = neg.lower_bound(mini);
      if (it == neg.begin()) {
        continue;
      }
      --it;
      ll ind = *it;
      assert(neg.count(ind));
      assert(a[ind] == -1);
      a[ind] = +1;
      neg.erase(ind);
      pos.insert(ind);
      upd(ind + 1, n, +2);
    } else {
      ll maxv;
      ll maxi;
      tie(maxv, maxi) = qmax(0, n);
      auto it = pos.lower_bound(maxi);
      if (it == pos.begin()) {
        continue;
      }
      --it;
      ll ind = *it;
      assert(pos.count(ind));
      assert(a[ind] == +1);
      a[ind] = -1;
      pos.erase(ind);
      neg.insert(ind);
      upd(ind + 1, n, -2);
    }
    answer = min(answer, qmax(0, n).first - qmin(0, n).first);
  }
  cout << answer << "\n";
  return 0;
}
