#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
const int inf=2147483547;
int n;
#define Maxn 1000010
char S[Maxn];
int sum[Maxn],at[Maxn],cnt=0;
int le[Maxn],ri[Maxn];

inline int D(int x){
    if(x>0)return x;
	return -x;	
}
inline bool Judge(int mid){
	le[0]=0;ri[0]=mid;
	for(int i=1;i<=cnt;++i){
		le[i]=-inf;ri[i]=inf;
	}
	for(int i=0;i<=n;++i){
		le[at[i]]=max(le[at[i]],-sum[i]); 
		ri[at[i]]=min(ri[at[i]],mid-sum[i]);
	}
	if(le[0]>ri[0])return false;
	int l,r,ty;
	if(le[0]==ri[0]){
		l=r=le[0];
		ty=(D(le[0])%2);
	}else{
		l=le[0];r=ri[0];
		ty=2;
	}
	for(int i=1;i<=cnt;++i){
		if(ty==2){
			l--;r++;
			l=max(l,le[i]);r=min(r,ri[i]);
			if(l>r)return false;
			if(l==r){
				ty=(D(l)%2);
				continue;
			}
			continue;
		}
		l--;r++;
		l=max(l,le[i]);r=min(r,ri[i]);
		if(l>r)return false;
		int g=(D(l)%2);
		ty^=1;
		if(l+(g^ty)>r)return false;
	}
	return true;
}

int main(){
	scanf("%s",S+1);n=strlen(S+1);
	cnt=0;
	for(int i=1;i<=n;++i){
		sum[i]+=sum[i-1];
	    if(S[i]=='1')
	       sum[i]++;	
	    if(S[i]=='0')
		sum[i]--;
		if(S[i]=='?')cnt++;
		at[i]=cnt; 
	}
	int l=0,r=n;
	while(l<r){
		int mid=(l+r)>>1;
		if(Judge(mid))r=mid;
		else l=mid+1;
	}
	printf("%d\n",l);
	return 0;
}