#include <bits/stdc++.h>
#define rep(i,n) for(int i = 0; i < (n); ++i)
#define srep(i,s,t) for (int i = s; i < t; ++i)
#define drep(i,n) for(int i = (n)-1; i >= 0; --i)
using namespace std;
typedef long long int ll;
typedef pair<int,int> P;
#define yn {puts("Yes");}else{puts("No");}
#define MAX_N 200005

int main() {
    string s;
    cin >> s;
    int ans = 1001001001;
    int n = s.size();
    int l = 0, r = 1001001;

    if(n == 1){
        cout << 1 << endl;
        return 0;
    }

    int line[n] = {};
    int gg[n] = {};
    drep(i,n-1){
        if(s[i+1] == '0'){
            line[i] = line[i+1] + 1;
        }else{
            line[i] = max(0, line[i+1] - 1);
        }
        if(s[i+1] == '1'){
            gg[i] = gg[i+1] + 1;
        }else{
            gg[i] = max(0, gg[i+1] - 1);
        }
    }

    
    // rep(i,n)cout << gg[i] << ' ';
    // cout << endl;

    l = 0;
    r = 1001001;

    while(l + 1 < r){
        int m =(l + r) / 2;
        int flag = 1;
        int now = 0;
        int nowleft = 0;
        int ff[n] = {};
        rep(i,n){
            ff[i] = line[i];
        }
        rep(i,n){
            if(s[i] == '0'){
                now = max(0, now-1);
                nowleft--;
                if(nowleft - ff[i] < -m){
                    flag = 0;
                    break;
                }
            }else if(s[i] == '1'){
                now++;
                nowleft = min(nowleft + 1, 0);
                if(now > m){
                    flag = 0;
                    break;
                }
            }else{
                if(nowleft - ff[i] <= -m){
                    now++;
                    nowleft = min(nowleft + 1, 0);
                }else if(gg[i] + 2 > m && i < n-1 && s[i+1] == '?'){
                    now++;
                    nowleft = min(nowleft + 1, 0);
                }else{
                    now = max(0, now-1);
                    nowleft--;
                }
            }
            if(nowleft - ff[i] < -m){
                flag = 0;
                break;
            }
            if(now > m){
                flag = 0;
                break;
            }
            /*
            if(m == 2){
                cout << now << ' ' << nowleft << endl;
            }
            */
        }

        if(flag == 1)r = m;
        else l = m;
    }
    ans = min(ans, r);











    l = 0;
    r = 1001001;

    while(l + 1 < r){
        int m =(l + r) / 2;
        int flag = 1;
        int now = 0;
        int nowleft = 0;
        int ff[n] = {};
        rep(i,n){
            ff[i] = line[i];
        }
        rep(i,n){
            if(s[i] == '0'){
                now = max(0, now-1);
                nowleft--;
                if(nowleft - ff[i] < -m){
                    flag = 0;
                    break;
                }
            }else if(s[i] == '1'){
                now++;
                nowleft = min(nowleft + 1, 0);
                if(now > m){
                    flag = 0;
                    break;
                }
            }else{

                if(-(nowleft - ff[i]) >= now + gg[i]){
                    now++;
                    nowleft = min(nowleft + 1, 0);
                }else{
                    now = max(0, now-1);
                    nowleft--;
                }
                /*
                if(nowleft - ff[i] <= -m){
                    now++;
                    nowleft = min(nowleft + 1, 0);
                }else if(gg[i] + 2 > m && i < n-1 && s[i+1] == '?'){
                    now++;
                    nowleft = min(nowleft + 1, 0);
                }else{
                    now = max(0, now-1);
                    nowleft--;
                }
                */
            }
            if(nowleft < -m){
                flag = 0;
                break;
            }
            if(now > m){
                flag = 0;
                break;
            }
            /*
            if(m == 2){
                cout << now << ' ' << nowleft << endl;
            }
            */
        }

        if(flag == 1)r = m;
        else l = m;
    }
    ans = min(ans, r);












    l = 0;
    r = 1001001;

    while(l + 1 < r){
        int m =(l + r) / 2;
        int flag = 1;
        int now = 0;
        int nowleft = 0;
        int ff[n] = {};
        rep(i,n){
            ff[i] = line[i];
        }
        rep(i,n){
            if(s[i] == '0'){
                now = max(0, now-1);
                nowleft--;
                if(nowleft - ff[i] < -m){
                    flag = 0;
                    break;
                }
            }else if(s[i] == '1'){
                now++;
                nowleft = min(nowleft + 1, 0);
                if(now > m){
                    flag = 0;
                    break;
                }
            }else{

                if(-(nowleft - ff[i]) > now + gg[i]){
                    now++;
                    nowleft = min(nowleft + 1, 0);
                }else{
                    now = max(0, now-1);
                    nowleft--;
                }
                /*
                if(nowleft - ff[i] <= -m){
                    now++;
                    nowleft = min(nowleft + 1, 0);
                }else if(gg[i] + 2 > m && i < n-1 && s[i+1] == '?'){
                    now++;
                    nowleft = min(nowleft + 1, 0);
                }else{
                    now = max(0, now-1);
                    nowleft--;
                }
                */
            }
            if(nowleft < -m){
                flag = 0;
                break;
            }
            if(now > m){
                flag = 0;
                break;
            }
            /*
            if(m == 2){
                cout << now << ' ' << nowleft << endl;
            }
            */
        }

        if(flag == 1)r = m;
        else l = m;
    }
    ans = min(ans, r);





















    int r1 = r;

    l = 0;
    r = 1001001;

    while(l + 1 < r){
        int m =(l + r) / 2;
        int flag = 1;
        int now = 0;
        int nowleft = 0;
        int ff[n] = {};
        rep(i,n){
            ff[i] = line[i];
        }
        rep(i,n){
            if(s[i] == '0'){
                now = max(0, now-1);
                nowleft--;
                if(nowleft - ff[i] < -m){
                    flag = 0;
                    break;
                }
            }else if(s[i] == '1'){
                now++;
                nowleft = min(nowleft + 1, 0);
                if(now > m){
                    flag = 0;
                    break;
                }
            }else{
                if(nowleft - ff[i] <= -m){
                    now++;
                    nowleft = min(nowleft + 1, 0);
                }else{
                    now = max(0, now-1);
                    nowleft--;
                }
            }
            if(nowleft - ff[i] < -m){
                flag = 0;
                break;
            }
            if(now > m){
                flag = 0;
                break;
            }
        }

        if(flag == 1)r = m;
        else l = m;
    }
    ans = min(ans, r);

    reverse(s.begin(), s.end());

    rep(i,n)line[i] = 0;
    rep(i,n)gg[i] = 0;
    drep(i,n-1){
        if(s[i+1] == '0'){
            line[i] = line[i+1] + 1;
        }else{
            line[i] = max(0, line[i+1] - 1);
        }
        if(s[i+1] == '1'){
            gg[i] = gg[i+1] + 1;
        }else{
            gg[i] = max(0, gg[i+1] - 1);
        }
    }
    
    // rep(i,n)cout << line[i] << ' ';

    l = 0;
    r = 1001001;

    while(l + 1 < r){
        int m =(l + r) / 2;
        int flag = 1;
        int now = 0;
        int nowleft = 0;
        int ff[n] = {};
        rep(i,n){
            ff[i] = line[i];
        }
        rep(i,n){
            if(s[i] == '0'){
                now = max(0, now-1);
                nowleft--;
                if(nowleft - ff[i] < -m){
                    flag = 0;
                    break;
                }
            }else if(s[i] == '1'){
                now++;
                nowleft = min(nowleft + 1, 0);
                if(now > m){
                    flag = 0;
                    break;
                }
            }else{
                if(nowleft - ff[i] <= -m){
                    now++;
                    nowleft = min(nowleft + 1, 0);
                }else{
                    now = max(0, now-1);
                    nowleft--;
                }
            }
            if(nowleft - ff[i] < -m){
                flag = 0;
                break;
            }
            if(now > m){
                flag = 0;
                break;
            }
        }

        if(flag == 1)r = m;
        else l = m;
    }
    ans = min(ans, r);
    int r2 = r;

    // cout << r1 << ' ' << r2 << ' ' << ans << endl;


    l = 0;
    r = 1001001;

    while(l + 1 < r){
        int m =(l + r) / 2;
        int flag = 1;
        int now = 0;
        int nowleft = 0;
        int ff[n] = {};
        rep(i,n){
            ff[i] = line[i];
        }
        rep(i,n){
            if(s[i] == '0'){
                now = max(0, now-1);
                nowleft--;
                if(nowleft - ff[i] < -m){
                    flag = 0;
                    break;
                }
            }else if(s[i] == '1'){
                now++;
                nowleft = min(nowleft + 1, 0);
                if(now > m){
                    flag = 0;
                    break;
                }
            }else{
                if(nowleft - ff[i] <= -m){
                    now++;
                    nowleft = min(nowleft + 1, 0);
                }else if(gg[i] + 2 > m && i < n-1 && s[i+1] == '?'){
                    now++;
                    nowleft = min(nowleft + 1, 0);
                }else{
                    now = max(0, now-1);
                    nowleft--;
                }
            }
            if(nowleft - ff[i] < -m){
                flag = 0;
                break;
            }
            if(now > m){
                flag = 0;
                break;
            }
            /*
            if(m == 2){
                cout << now << ' ' << nowleft << endl;
            }
            */
        }

        if(flag == 1)r = m;
        else l = m;
    }
    ans = min(ans, r);













    l = 0;
    r = 1001001;

    while(l + 1 < r){
        int m =(l + r) / 2;
        int flag = 1;
        int now = 0;
        int nowleft = 0;
        int ff[n] = {};
        rep(i,n){
            ff[i] = line[i];
        }
        rep(i,n){
            if(s[i] == '0'){
                now = max(0, now-1);
                nowleft--;
                if(nowleft - ff[i] < -m){
                    flag = 0;
                    break;
                }
            }else if(s[i] == '1'){
                now++;
                nowleft = min(nowleft + 1, 0);
                if(now > m){
                    flag = 0;
                    break;
                }
            }else{

                if(-(nowleft - ff[i]) >= now + gg[i]){
                    now++;
                    nowleft = min(nowleft + 1, 0);
                }else{
                    now = max(0, now-1);
                    nowleft--;
                }
                /*
                if(nowleft - ff[i] <= -m){
                    now++;
                    nowleft = min(nowleft + 1, 0);
                }else if(gg[i] + 2 > m && i < n-1 && s[i+1] == '?'){
                    now++;
                    nowleft = min(nowleft + 1, 0);
                }else{
                    now = max(0, now-1);
                    nowleft--;
                }
                */
            }
            if(nowleft < -m){
                flag = 0;
                break;
            }
            if(now > m){
                flag = 0;
                break;
            }
            /*
            if(m == 2){
                cout << now << ' ' << nowleft << endl;
            }
            */
        }

        if(flag == 1)r = m;
        else l = m;
    }
    ans = min(ans, r);







    l = 0;
    r = 1001001;

    while(l + 1 < r){
        int m =(l + r) / 2;
        int flag = 1;
        int now = 0;
        int nowleft = 0;
        int ff[n] = {};
        rep(i,n){
            ff[i] = line[i];
        }
        rep(i,n){
            if(s[i] == '0'){
                now = max(0, now-1);
                nowleft--;
                if(nowleft - ff[i] < -m){
                    flag = 0;
                    break;
                }
            }else if(s[i] == '1'){
                now++;
                nowleft = min(nowleft + 1, 0);
                if(now > m){
                    flag = 0;
                    break;
                }
            }else{

                if(-(nowleft - ff[i]) > now + gg[i]){
                    now++;
                    nowleft = min(nowleft + 1, 0);
                }else{
                    now = max(0, now-1);
                    nowleft--;
                }
                /*
                if(nowleft - ff[i] <= -m){
                    now++;
                    nowleft = min(nowleft + 1, 0);
                }else if(gg[i] + 2 > m && i < n-1 && s[i+1] == '?'){
                    now++;
                    nowleft = min(nowleft + 1, 0);
                }else{
                    now = max(0, now-1);
                    nowleft--;
                }
                */
            }
            if(nowleft < -m){
                flag = 0;
                break;
            }
            if(now > m){
                flag = 0;
                break;
            }
            /*
            if(m == 2){
                cout << now << ' ' << nowleft << endl;
            }
            */
        }

        if(flag == 1)r = m;
        else l = m;
    }
    ans = min(ans, r);





    

    cout << ans << endl;
    return 0;
}




Measured memory_bytes: 16116