#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int MX = 1e6 + 5;
const long long INF = 1e18;
const long double PI = acos((long double)-1);
const int xd[4] = {1, 0, -1, 0}, yd[4] = {0, 1, 0, -1};
mt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());
template <class T>
bool ckmin(T& a, const T& b) {
  return b < a ? a = b, 1 : 0;
}
template <class T>
bool ckmax(T& a, const T& b) {
  return a < b ? a = b, 1 : 0;
}
int pct(int x) { return __builtin_popcount(x); }
int bits(int x) { return 31 - __builtin_clz(x); }
int cdiv(int a, int b) { return a / b + !(a < 0 || a % b == 0); }
int fstTrue(function<bool(int)> first, int lo, int hi) {
  hi++;
  assert(lo <= hi);
  while (lo < hi) {
    int mid = (lo + hi) / 2;
    first(mid) ? hi = mid : lo = mid + 1;
  }
  return lo;
}
template <class A>
void re(complex<A>& c);
template <class A, class B>
void re(pair<A, B>& p);
template <class A>
void re(vector<A>& v);
template <class A, size_t SZ>
void re(array<A, SZ>& a);
template <class T>
void re(T& x) {
  cin >> x;
}
void re(double& d) {
  string t;
  re(t);
  d = stod(t);
}
void re(long double& d) {
  string t;
  re(t);
  d = stold(t);
}
template <class H, class... T>
void re(H& h, T&... t) {
  re(h);
  re(t...);
}
template <class A>
void re(complex<A>& c) {
  A a, b;
  re(a, b);
  c = {a, b};
}
template <class A, class B>
void re(pair<A, B>& p) {
  re(p.first, p.second);
}
template <class A>
void re(vector<A>& x) {
  for (auto& a : x) re(a);
}
template <class A, size_t SZ>
void re(array<A, SZ>& x) {
  for (auto& a : x) re(a);
}
string to_string(char c) { return string(1, c); }
string to_string(bool b) { return b ? "true" : "false"; }
string to_string(const char* second) { return (string)second; }
string to_string(string second) { return second; }
template <class A>
string to_string(complex<A> c) {
  stringstream ss;
  ss << c;
  return ss.string();
}
string to_string(vector<bool> v) {
  string res = "{";
  for (int i = (0); i < ((int)v.size()); ++i) res += char('0' + v[i]);
  res += "}";
  return res;
}
template <size_t SZ>
string to_string(bitset<SZ> b) {
  string res = "";
  for (int i = (0); i < (SZ); ++i) res += char('0' + b[i]);
  return res;
}
template <class A, class B>
string to_string(pair<A, B> p);
template <class T>
string to_string(T v) {
  bool fst = 1;
  string res = "{";
  for (const auto& x : v) {
    if (!fst) res += ", ";
    fst = 0;
    res += to_string(x);
  }
  res += "}";
  return res;
}
template <class A, class B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <class A>
void pr(A x) {
  cout << to_string(x);
}
template <class H, class... T>
void pr(const H& h, const T&... t) {
  pr(h);
  pr(t...);
}
void ps() { pr("\n"); }
template <class H, class... T>
void ps(const H& h, const T&... t) {
  pr(h);
  if (sizeof...(t)) pr(" ");
  ps(t...);
}
void DBG() { cerr << "]" << endl; }
template <class H, class... T>
void DBG(H h, T... t) {
  cerr << to_string(h);
  if (sizeof...(t)) cerr << ", ";
  DBG(t...);
}
void setIn(string second) { freopen(second.c_str(), "r", stdin); }
void setOut(string second) { freopen(second.c_str(), "w", stdout); }
void unsyncIO() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
}
void setIO(string second = "") {
  unsyncIO();
  if ((int)second.size()) {
    setIn(second + ".in"), setOut(second + ".out");
  }
}
template <class T, int SZ>
struct LazySeg {
  T mn[2 * SZ], mx[2 * SZ], lazy[2 * SZ];
  LazySeg() {
    for (int i = (0); i < (2 * SZ); ++i) mn[i] = mx[i] = lazy[i] = 0;
  }
  void push(int ind, int L, int R) {
    if (L != R)
      for (int i = (0); i < (2); ++i) lazy[2 * ind + i] += lazy[ind];
    mn[ind] += lazy[ind];
    mx[ind] += lazy[ind];
    lazy[ind] = 0;
  }
  void pull(int ind) {
    mn[ind] = min(mn[2 * ind], mn[2 * ind + 1]);
    mx[ind] = max(mx[2 * ind], mx[2 * ind + 1]);
  }
  void build() {
    for (int i = (SZ)-1; i >= (1); --i) pull(i);
  }
  void upd(int lo, int hi, T inc, int ind = 1, int L = 0, int R = SZ - 1) {
    push(ind, L, R);
    if (hi < L || R < lo) return;
    if (lo <= L && R <= hi) {
      lazy[ind] = inc;
      push(ind, L, R);
      return;
    }
    int M = (L + R) / 2;
    upd(lo, hi, inc, 2 * ind, L, M);
    upd(lo, hi, inc, 2 * ind + 1, M + 1, R);
    pull(ind);
  }
  T qmax(int lo, int hi, int ind = 1, int L = 0, int R = SZ - 1) {
    push(ind, L, R);
    if (lo > R || L > hi) return -INF;
    if (lo <= L && R <= hi) return mx[ind];
    int M = (L + R) / 2;
    return max(qmax(lo, hi, 2 * ind, L, M),
               qmax(lo, hi, 2 * ind + 1, M + 1, R));
  }
  T qmin(int lo, int hi, int ind = 1, int L = 0, int R = SZ - 1) {
    push(ind, L, R);
    if (lo > R || L > hi) return INF;
    if (lo <= L && R <= hi) return mn[ind];
    int M = (L + R) / 2;
    return min(qmin(lo, hi, 2 * ind, L, M),
               qmin(lo, hi, 2 * ind + 1, M + 1, R));
  }
  int getMin(T x, int ind = 1, int L = 0, int R = SZ - 1) {
    push(ind, L, R);
    if (mx[ind] <= x) return L;
    if (L == R) return MOD;
    int M = (L + R) / 2;
    int t = getMin(x, 2 * ind + 1, M + 1, R);
    if (t > M + 1) return t;
    int u = getMin(x, 2 * ind, L, M);
    return u == MOD ? t : u;
  }
};
LazySeg<long long, 1 << 20> L;
string S;
int main() {
  setIO();
  re(S);
  int lef = 0;
  set<int> change;
  for (int i = (0); i < ((int)S.size()); ++i) {
    if (S[i] == '?') {
      S[i] = '0';
      change.insert(i);
      lef++;
    }
    if (S[i] == '0')
      L.upd(i + 1, (1 << 20) - 1, -1);
    else
      L.upd(i + 1, (1 << 20) - 1, 1);
  }
  int bal = 0, mx = 0;
  for (auto& c : S) {
    if (c == '0')
      bal--;
    else
      bal++;
    ckmax(mx, bal);
  }
  long long ans = MOD;
  for (;; ++mx) {
    while ((int)change.size()) {
      int ind = L.getMin(mx - 2) - 1;
      auto it = change.lower_bound(ind);
      if (it == end(change)) break;
      int i = *it;
      change.erase(it);
      L.upd(i + 1, (1 << 20) - 1, 2);
    }
    ckmin(ans, mx - L.qmin(0, (1 << 20) - 1));
    if (!(int)change.size()) break;
  }
  ps(ans);
}
