#include<bits/stdc++.h>
using namespace std;

#define INF int(1e9)

const int maxn=1000005;
int n;
char s[maxn];

bool check(int d){
	pair<int,int>val[2]={make_pair(0,d),make_pair(0,d)};
	for(int i=0;i<n;i++){
		for(int j=0;j<2;j++){
			if(val[j].first%2!=j)val[j].first++;
			if(val[j].second%2!=j)val[j].second--;
		}
		pair<int,int>nval[2]={make_pair(INF,-INF),make_pair(INF,-INF)};
		for(int c=0;c<2;c++)if(s[i]=='?'||s[i]=='0'+c){
			for(int j=0;j<2;j++){
				int vl=val[j].first+2*c-1;
				int vr=val[j].second+2*c-1;
				vl=max(vl,0);
				vr=min(vr,d);
				if(vl>vr)continue;
				nval[j^1].first=min(nval[j^1].first,vl);
				nval[j^1].second=max(nval[j^1].second,vr);
			}
		}
		val[0]=nval[0];
		val[1]=nval[1];
	}
	for(int j=0;j<2;j++){
		if(val[j].first%2!=j)val[j].first++;
		if(val[j].second%2!=j)val[j].second--;
	}
	return val[0].first<=val[0].second||val[1].first<=val[1].second;
}

int main(){
	scanf("%s",s);n=strlen(s);
	int l=0,r=n;
	while(l<r){
		int mid=l+r>>1;
		if(check(mid))r=mid;
		else l=mid+1;
	}
	printf("%d\n",r);
	return 0;
} 