#include <bits/stdc++.h>

#define fi first
#define se second

const int N = 1000011;
const long long mod = 1e9 + 7;

using namespace std;

int n;
int mx[N];
string s;

int solve(int B)
{
        int cur = 0, A = 0;
        for(int i = 0; i < n; i++){
                if(s[i] == '0'){
                        cur -= 1;
                } else if(s[i] == '1'){
                        cur += 1;
                } else{
                        if(cur + 1 + max(0, mx[i + 1]) > B){
                                cur -= 1;
                        } else{
                                cur += 1;
                        }
                }
                A = min(A, cur);
        }
        return B - A;
}

int main()
{
        ios_base::sync_with_stdio(0);

        //freopen("input.txt", "r", stdin);
        //freopen("output.txt", "w", stdout);

        cin >> s;
        n = s.size();

        for(int i = n - 1; i >= 0; i--){
                mx[i] = max(0, mx[i + 1]) + (s[i] == '1' ? 1 : -1);
        }

        int l = 0, r = n;
        for(int i = 0, cur = 0; i < n; i++){
                cur += (s[i] == '1' ? 1 : -1);
                l = max(l, cur);
        }

        int res = solve(l);
        for(int i = 1; i <= 40; i++){
                if(i + l <= n){
                        res = min(res, solve(i + l));
                }
        }

        while(l + 40 < r){
                int m = (r - l) / 3;
                int h1 = l + m, h2 = r - m;
                if(solve(h1) < solve(h2)){
                        r = h2;
                } else{
                        l = h1;
                }
        }
        while(l <= r){
                res = min(res, solve(l));
                l += 1;
        }

        cout << res << "\n";
}
