#include <bits/stdc++.h>
using namespace std;
 
#define REP(i, n) for (ll i = 0; i < n; i++)
#define REPR(i, n) for (ll i = n; i >= 0; i--)
#define FOR(i, m, n) for (ll i = m; i < n; i++)
#define FORR(i, m, n) for (ll i = m; i >= n; i--)
#define REPO(i, n) for (ll i = 1; i <= n; i++)
#define ll long long
#define INF (ll)1 << 60
#define MINF (-1 * INF)
#define ALL(n) n.begin(), n.end()
#define MOD 1000000007
#define P pair<ll, ll>

string s;
ll n, ans = INF;
ll dp[1100000];
ll solve(ll ind){
    
    ll ma = 0, mi = 0, now = 0;
    REP(i, n){
        if (s[i] == '0') now--;
        if (s[i] == '1') now++;
        if (s[i] == '?'){
            if(now - 1 - dp[i] >= ind){
                now--;
            }
            else{
                now++;
            }
        }
        ma = max(now, ma);
        mi = min(now, mi);
    }
    //cout << ind << " " << abs(ma - mi) << endl;
    ans = min(ans, abs(ma - mi));
    return abs(ma - mi);
}
P sabu1(int from, int to) {
	for (;to - from > 1;) {
		int mid = (from + to) / 2;
		(solve(mid * 2) - solve((mid - 1) * 2) <= 0 ? from : to) = mid;
	}
	return P(from, to);
}
P sabu2(int from, int to) {
	for (;to - from > 30;) {
		int mid = (from + to) / 2;
		(solve(mid * 2 - 1) - solve((mid - 1) * 2 - 1) <= 0 ? from : to) = mid;
	}
	return P(from, to);
}
int main() {
    cin >> s;
    n = s.size();
    ll now = 0, mi = 0;
    REPR(i, n - 1){
        dp[i] = now - mi;
        if (s[i] == '0') now++;
        else now--;
        mi = min(now, mi);
        
    }
    P res = sabu1(-1e6 - 10, 1);
    FOR(i, res.first, res.second){
        solve(i);
    }
    P res = sabu2(-1e6 - 10, 1);
    FOR(i, res.first, res.second){
        solve(i);
    }
    cout << ans << endl;
}
