#include <bits/stdc++.h>
 
// headers {{{
using namespace std;
// using namespace rel_ops;
 
typedef long long int64;
typedef unsigned long long uint64;
const double pi=acos(-1.0);
const double eps=1e-11;
const int INF=0x7FFFFFFF;
template<class T> inline bool checkmin(T &a,T b){return b<a?a=b,1:0;}
template<class T> inline bool checkmax(T &a,T b){return b>a?a=b,1:0;}
template<class T> inline T sqr(T x){return x*x;}
typedef pair<int,int> PII;
typedef vector<int> VI;
typedef vector<PII> VII;
#define MP(A,B) make_pair(A,B)
#define PB(X) push_back(X)
#define mem(a,b) memset(a, b, sizeof(a))
#define clr(a) memset(a, 0, sizeof(a))
#define rep(i,n) for(int i=0; i<(int)n; i++)
#define ff first
#define ss second
#define sz(g) int(g.size())
#ifdef LOCAL
#define dbg(args...) printf(args); //##__VA_ARGS__
#define dout cout
#define out(x) (cout<<#x<<": "<<x<<endl)
template<class T>void show(T a, int n){for(int i=0; i<n; ++i) cout<<a[i]<<' '; cout<<endl;}
template<class T>void show(T a, int r, int l){for(int i=0; i<r; ++i)show(a[i],l);cout<<endl;}
#else
#define dbg(...)
#define dout if(true);else cout
#define out(...)
#define show(...)
#endif
// }}}

bool test(string& s, int mx) {
    int a = 0, b = 0;
    int n = sz(s);

    rep(i, n) {
        out(a); out(b);
        out(s[i]);
        if (s[i] == '0') {
            a--; b--;
            if (b < -mx) b +=  2;
            if (b > a) return false;
        } else if (s[i] == '1') {
            a++; b++;
            if (a > mx ) a -= 2;
            if (b > a) return false;
        } else {
            a++; b--;
            if (a > mx) a -= 2;
            if (b < -mx) b += 2;

            if (b > a) return false;
        }
    }
    return true;
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL); 
    string s;
    while (cin >> s) {
        int n = sz(s);
        // int l = 1, r = n;
       // auto x = test(s, 1);
        // out(x);
        // if (false) 
        // while (l <= r) {
            // int mid = (l+r)/2;
            // if (test(s, mid)) r = mid - 1;
            // else l = mid + 1;
        // }
        int minX = 0, maxX = 0;
        int sum = 0;
        VI prefix(n+1);
        rep(i, n) {
            if (s[i] == '0') sum--;
            else sum ++;
            prefix[i+1] = sum;
            checkmin(minX, sum);
            checkmax(maxX, sum);
        }
        out(n);
        show(prefix, sz(prefix));
        auto fun = [&](int d) {
            int maxL = 0;
            // for (int i = n; i >= 0; i--) if (prefix[i] == maxX) minR = i;
            for (int i = 0; i <= n; i++) if (prefix[i] == minX) maxL = i;
            VI right_max(n+1), right_min(n+1);
            auto pre = prefix;
            right_max[n] = right_min[n] = pre[n];
            for (int i = n-1; i >= 0; i--) {
                right_max[i] = max(right_max[i+1], pre[i]);
                right_min[i] = min(right_min[i+1], pre[i]);
            }
            show(right_min, n+1);
            int del = 0;
            for (int i = maxL + 1; i <= n; i++) {
                if (s[i-1] == '?' && del + right_min[i] - 2 >= minX - d) {
                    del -= 2;
                }
                out(del);
                pre[i] += del;
            }
            show(pre, n+1);
            int maxX = 0, minX = 0;
            for (int i = 0; i <= n; i++) checkmax(maxX, pre[i]);
            for (int i = 0; i <= n; i++) checkmin(minX, pre[i]);

            return maxX - minX;
        };
        cout << min(fun(0), fun(1)) << endl;
    }
    return 0;
}



Measured memory_bytes: 19860