#include <bits/stdc++.h>
using namespace std;
const int Inf = 1e9 + 7;
const int N = 1e6 + 7;
template <class t>
using vc = vector<t>;
template <class t>
using vvc = vc<vc<t>>;
int popcnt(uint x) { return __builtin_popcount(x); }
int popcnt(unsigned long long x) { return __builtin_popcountll(x); }
int bsr(uint x) { return 31 - __builtin_clz(x); }
int bsr(unsigned long long x) { return 63 - __builtin_clzll(x); }
int bsf(uint x) { return __builtin_ctz(x); }
int bsf(unsigned long long x) { return __builtin_ctzll(x); }
struct FastSet {
  static constexpr uint B = 64;
  int n, lg;
  vvc<unsigned long long> seg;
  FastSet(int _n, unsigned long long val = 0) : n(_n) {
    do {
      seg.push_back(vc<unsigned long long>((_n + B - 1) / B, val));
      _n = (_n + B - 1) / B;
    } while (_n > 1);
    lg = seg.size();
  }
  bool operator[](int i) const { return (seg[0][i / B] >> (i % B) & 1) != 0; }
  void set(int i) {
    for (int h = 0; h < lg; h++) {
      seg[h][i / B] |= 1ULL << (i % B);
      i /= B;
    }
  }
  void reset(int i) {
    for (int h = 0; h < lg; h++) {
      seg[h][i / B] &= ~(1ULL << (i % B));
      if (seg[h][i / B]) break;
      i /= B;
    }
  }
  int next(int i) {
    for (int h = 0; h < lg; h++) {
      if (i / B == seg[h].size()) break;
      unsigned long long d = seg[h][i / B] >> (i % B);
      if (!d) {
        i = i / B + 1;
        continue;
      }
      i += bsf(d);
      for (int g = h - 1; g >= 0; g--) {
        i *= B;
        i += bsf(seg[g][i / B]);
      }
      return i;
    }
    return n;
  }
  int prev(int i) {
    i--;
    for (int h = 0; h < lg; h++) {
      if (i == -1) break;
      unsigned long long d = seg[h][i / B] << (63 - i % 64);
      if (!d) {
        i = i / B - 1;
        continue;
      }
      i += bsr(d) - (B - 1);
      for (int g = h - 1; g >= 0; g--) {
        i *= B;
        i += bsr(seg[g][i / B]);
      }
      return i;
    }
    return -1;
  }
};
struct SegmentTree {
  struct Node {
    int mn, mn_id, mx, mx_id;
    Node(int x, int id) {
      mn = mx = x;
      mn_id = mx_id = id;
    }
    Node() { mn = Inf, mx = -Inf, mn_id = -1, mx_id = -1; }
    Node operator+(const Node &other) {
      Node res;
      res.mn = min(mn, other.mn);
      res.mx = max(mx, other.mx);
      if (res.mn == mn) {
        res.mn_id = max(res.mn_id, mn_id);
      }
      if (res.mx == mx) {
        res.mx_id = max(res.mx_id, mx_id);
      }
      if (res.mn == other.mn) {
        res.mn_id = max(res.mn_id, other.mn_id);
      }
      if (res.mx == other.mx) {
        res.mx_id = max(res.mx_id, other.mx_id);
      }
      return res;
    }
  };
  Node t[4 * N];
  int mod[4 * N];
  void update(int v, int val) {
    t[v].mn += val;
    t[v].mx += val;
    mod[v] += val;
  }
  void push(int v) {
    if (mod[v]) {
      update(2 * v + 1, mod[v]);
      update(2 * v + 2, mod[v]);
      mod[v] = 0;
    }
  }
  void modify(int ql, int qr, int val, int l = 0, int r = N - 1, int v = 0) {
    if (qr < l || r < ql) return;
    if (ql <= l && r <= qr) {
      update(v, val);
    } else {
      push(v);
      int m = (l + r) >> 1;
      modify(ql, qr, val, l, m, 2 * v + 1);
      modify(ql, qr, val, m + 1, r, 2 * v + 2);
      t[v] = t[2 * v + 1] + t[2 * v + 2];
    }
  }
  int get_last(int l = 0, int r = N - 1, int v = 0) {
    if (l == r) {
      if (t[v].mn >= 2) {
        return l;
      } else {
        return -1;
      }
    }
    push(v);
    int m = (l + r) >> 1;
    if (t[2 * v + 1].mn < 2) {
      return get_last(l, m, 2 * v + 1);
    } else {
      int id = get_last(m + 1, r, 2 * v + 2);
      if (id != -1)
        return id;
      else
        return m;
    }
  }
  void change(int id, int l = 0, int r = N - 1, int v = 0) {
    if (l == r) {
      t[v] = Node(0, id);
    } else {
      push(v);
      int m = (l + r) >> 1;
      if (id <= m) {
        change(id, l, m, 2 * v + 1);
      } else {
        change(id, m + 1, r, 2 * v + 2);
      }
      t[v] = t[2 * v + 1] + t[2 * v + 2];
    }
  }
  SegmentTree() {
    fill(t, t + 4 * N, Node());
    fill(mod, mod + 4 * N, 0);
  }
};
vector<int> solve(string s) {
  int n = s.size();
  vector<int> mx(n + 1, Inf);
  mx[0] = 0;
  FastSet can_add(n), can_del(n);
  SegmentTree tr;
  auto balance = [&]() {
    while (tr.t[0].mn < 0) {
      int id = tr.t[0].mn_id;
      int ch_id = can_add.next(id);
      if (ch_id == n) break;
      can_add.reset(ch_id);
      can_del.set(ch_id);
      tr.modify(0, ch_id, 2);
    }
    while (tr.get_last() != -1) {
      int id = tr.get_last();
      int ch_id = can_del.prev(id + 1);
      if (ch_id == -1) break;
      can_del.reset(ch_id);
      can_add.set(ch_id);
      tr.modify(0, ch_id, -2);
    }
  };
  auto add = [&](int i) {
    tr.change(i + 1);
    if (s[i] == '1') {
      tr.modify(0, i, 1);
    } else if (s[i] == '0') {
      tr.modify(0, i, -1);
    } else {
      tr.modify(0, i, 1);
      can_del.set(i);
    }
    balance();
    if (tr.t[0].mn >= 0)
      return tr.t[0].mx;
    else
      return Inf;
  };
  tr.change(0);
  for (int i = 0; i < n; ++i) {
    mx[i + 1] = add(i);
  }
  return mx;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  string s;
  cin >> s;
  int n = s.size();
  for (char &c : s) {
    if (c == '0')
      c = '1';
    else if (c == '1')
      c = '0';
  }
  vector<int> pref = solve(s);
  for (char &c : s) {
    if (c == '0')
      c = '1';
    else if (c == '1')
      c = '0';
  }
  reverse(s.begin(), s.end());
  vector<int> suf = solve(s);
  reverse(suf.begin(), suf.end());
  reverse(s.begin(), s.end());
  int ans = Inf;
  for (int i = 0; i <= n; ++i) {
    ans = min(ans, max(pref[i], suf[i]));
  }
  cout << ans << '\n';
}
