#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define ULL unsigned long long
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define pll pair<LL,LL>
#define x first
#define y second
#define pi acosl(-1)
#define sqr(x) ((x)*(x))
#define pdd pair<double,double>
#define MEMS(x) memset(x,-1,sizeof(x))
#define MEM(x) memset(x,0,sizeof(x))
#define EPS 1e-4
#define arg ARG
#define cpdd const pdd
#define rank Rank
#define MAXN 205
//#define N 262144
#define ULL unsigned long long
#define ll long long
struct node{
    node *l,*r;
    int a,b;
    int add;
    int Min;
    int Max;
    int pos;
    node(int _a,int _b):a(_a),b(_b),l(NULL),r(NULL),add(0),Min(0),Max(0),pos(0){

    }
}*root;
int Min(node *n){
    return n->add+n->Min;
}
int Max(node *n){
    return n->add+n->Max;
}
void pull(node *n){
    n->Min=min(Min(n->l),Min(n->r));
    if(Max(n->l)>=Max(n->r)){
        n->pos=n->l->pos;
        n->Max=Max(n->l);
    }
    else{
        n->pos=n->r->pos;
        n->Max=Max(n->r);
    }
}
void push(node *n){
    n->l->add+=n->add;
    n->r->add+=n->add;
    n->add=0;
}
void build(node *n,int *a){
    if(n->a==n->b){
        n->Min=a[n->a];
        n->Max=a[n->a];
        n->pos=n->a;
     //   printf("?%d %d\n",n->a,a[n->a]);
        return ;
    }
    int mid=(n->a+n->b)/2;
    n->l=new node(n->a,mid);
    n->r=new node(mid+1,n->b);
    build(n->l,a);
    build(n->r,a);
    pull(n);
  //  printf("!%d %d %d %d\n",n->a,n->b,n->Min,n->Max);
}
void add(node *n,int l,int r,int k){
    if(n->a>=l&&n->b<=r){
        n->add+=k;
        return ;
    }
    if(n->b<l||n->a>r)return ;
    push(n);
    add(n->l,l,r,k);
    add(n->r,l,r,k);
    pull(n);
}
int main(){
    char c2[1000005];
    scanf("%s",c2+1);
    int ans=1e9;
    for(int xx = 0;xx<2;xx++){
        char c[1000005];
        MEM(c);
        for(int j=1;c2[j]!=0;j++)c[j]=c2[j];
        int a[1000005];
        a[0]=0;
        int n=strlen(c+1);
        set<int> s;
        for(int i = 1;c[i]!=0;i++){
            if(c[i]=='0')a[i]=a[i-1]-1;
            else a[i]=a[i-1]+1;
            if(c[i]=='?')s.insert(i),c[i]='1';
        }
        root=new node(0,n);
        build(root,a);
        ans=min(ans,Max(root)-Min(root));
      /*  printf("%s\n",c+1);
         int now=0;
            for(int i = 0;i<=n;i++){
                printf("%d ",now);
                if(c[i+1]=='0')now--;
                else now++;
            }
            //printf("\n%d %d\n",Max(root),Min(root));
        printf("\n%d %d\n",Max(root),Min(root));*/
       // int xx=Max(root);
        vector<int> v;
        while(true){
            int x=root->pos;
            if(s.upper_bound(x)==s.begin())break;
            auto it=prev(s.upper_bound(x));
            c[*it]='0';
            add(root,*it,n,-2);
            if(v.size()){
                //  printf("add %d\n",v.back());
                int now=Max(root);
                    add(root,v.back(),n,2);
                    if((Max(root)&1)!=xx){add(root,v.back(),n,-2);
						 if((Max(root)&1)!=xx){
                       //   printf("add %d\n",*it);
                          v.pb(*it);
                      }
                    }
                    else{
                    c[v.back()]='1';
                    v.pop_back();
                    }
                }
            else if((Max(root)&1)!=xx){
             //   printf("add %d\n",*it);
                v.pb(*it);
            }
           // else 
           /* else{
                
            }*/
        //  printf("%d %d\n",Max(root),Min(root));
            ans=min(ans,Max(root)-Min(root));
            s.erase(it);
           /* printf("%s\n",c+1);
            int now=0;
            for(int i = 0;i<=n;i++){
                printf("%d ",now);
                if(c[i+1]=='0')now--;
                else now++;
            }
            printf("\n%d %d\n",Max(root),Min(root));*/
        }
    }
    printf("%d\n",ans);
}
/*
1000000000000000000
1000000000000000000 1 1 1 1000000000
*/


Measured memory_bytes: 243912