#include<bits/stdc++.h>
#define re register
using namespace std;
inline int read(){
	re int t=0;re char v=getchar();
	while(v<'0')v=getchar();
	while(v>='0')t=(t<<3)+(t<<1)+v-48,v=getchar();
	return t;
}
char s[1000002];
int n;
inline bool dfs(re int x,re int y,re int mn,re int mx,re int num){
	if(abs(y-mn)>num||abs(y-mx)>num)return 0;
	re bool ans=0;
	if(x>n)ans=1;
	if(!ans&&s[x]!='1')ans|=dfs(x+1,y-1,min(mn,y-1),mx,num);
	if(!ans&&s[x]!='0')ans|=dfs(x+1,y+1,mn,max(mx,y+1),num);
	return ans;
}
inline bool check(re int x){
	return dfs(1,0,0,0,x);
}
signed main(){
	scanf("%s",s+1);
	n=strlen(s+1);
	int l=1,r=n,ans=n;
	while(l<=r){
		re int mid=l+r>>1;
		if(check(mid))ans=mid,r=mid-1;
		else l=mid+1;
	}
	printf("%lld",ans);
}