#include<bits/stdc++.h>
#define For(i,x,y) for (register int i=(x);i<=(y);i++)
#define FOR(i,x,y) for (register int i=(x);i<(y);i++)
#define Dow(i,x,y) for (register int i=(x);i>=(y);i--)
#define Debug(v) for (auto i:v) printf("%lld ",i);puts("")
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define ep emplace_back
#define siz(x) ((int)(x).size())
#define all(x) (x).begin(),(x).end()
#define fil(a,b) memset((a),(b),sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pa;
typedef pair<ll,ll> PA;
typedef vector<int> poly;
inline ll read(){
    ll x=0,f=1;char c=getchar();
    while ((c<'0'||c>'9')&&(c!='-')) c=getchar();
    if (c=='-') f=-1,c=getchar();
    while (c>='0'&&c<='9') x=x*10+c-'0',c=getchar();
    return x*f;
}

const int N = 1e6+10;
int n,suf[N][2];
char s[N];

inline int calc10(int x){
	if (suf[1][0]>x) return 1e9;
	int s=0,s2=0,mx2=0;
	For(i,1,n){
		if (::s[i]=='0'){
			s++,s2=max(0,s2-1);	
		} else if (::s[i]=='1'){
			s2++,mx2=max(mx2,s2);
			s=max(0,s-1);
		} else {
			if (s+1+suf[i+1][0]>x){
				s2++,mx2=max(mx2,s2);
				s=max(0,s-1);
			} else {
				s++,s2=max(0,s2-1);
			}
		}
		if (s+suf[i+1][0]>x) return 1e9;
	}
	return mx2;
}
inline int calc01(int x){
	if (suf[1][1]>x) return 1e9;
	int s=0,s2=0,mx2=0;
	For(i,1,n){
		if (::s[i]=='1'){
			s++,s2=max(0,s2-1);	
		} else if (::s[i]=='0'){
			s2++,mx2=max(mx2,s2);
			s=max(0,s-1);
		} else {
			if (s+1+suf[i+1][1]>x){
				s2++,mx2=max(mx2,s2);
				s=max(0,s-1);
			} else {
				s++,s2=max(0,s2-1);
			}
		}
		if (s+suf[i+1][1]>x) return 1e9;
	}
	return mx2;
}

int pre[N][2];
inline int _calc10(int x){
	if (suf[1][0]>x) return 1e9;
	int s=0,s2=0,mx2=0;
	Dow(i,n,1){
		if (::s[i]=='0'){
			s++,s2=max(0,s2-1);	
		} else if (::s[i]=='1'){
			s2++,mx2=max(mx2,s2);
			s=max(0,s-1);
		} else {
			if (s+1+pre[i-1][0]>x){
				s2++,mx2=max(mx2,s2);
				s=max(0,s-1);
			} else {
				s++,s2=max(0,s2-1);
			}
		}
		if (s+pre[i-1][0]>x) return 1e9;
	}
	return mx2;
}
inline int _calc01(int x){
	if (suf[1][1]>x) return 1e9;
	int s=0,s2=0,mx2=0;
	Dow(i,n,1){
		if (::s[i]=='1'){
			s++,s2=max(0,s2-1);	
		} else if (::s[i]=='0'){
			s2++,mx2=max(mx2,s2);
			s=max(0,s-1);
		} else {
			if (s+1+pre[i-1][1]>x){
				s2++,mx2=max(mx2,s2);
				s=max(0,s-1);
			} else {
				s++,s2=max(0,s2-1);
			}
		}
		if (s+pre[i-1][1]>x) return 1e9;
	}
	return mx2;
}

int main(){
	scanf("%s",s+1),n=strlen(s+1);
	Dow(i,n,1){
		if (s[i]=='0'){
			suf[i][0]=suf[i+1][0]+1;
			suf[i][1]=max(0,suf[i+1][1]-1);
		} else if (s[i]=='1'){
			suf[i][0]=max(0,suf[i+1][0]-1);
			suf[i][1]=suf[i+1][1]+1;
		} else {
			suf[i][0]=max(0,suf[i+1][0]-1);
			suf[i][1]=max(0,suf[i+1][1]-1);
		}
	}
	For(i,1,n){
		if (s[i]=='0'){
			pre[i][0]=pre[i-1][0]+1;
			pre[i][1]=max(0,pre[i-1][1]-1);
		} else if (s[i]=='1'){
			pre[i][0]=max(0,pre[i-1][0]-1);
			pre[i][1]=pre[i-1][1]+1;
		} else {
			pre[i][0]=max(0,pre[i-1][0]-1);
			pre[i][1]=max(0,pre[i-1][1]-1);
		}
	}
	int ans=n;
	int l=0,r=n,ret=-1;
	while (l<=r){
		int mid=l+r>>1;
		if (calc10(mid)<=mid) ret=mid,r=mid-1;
			else l=mid+1;
	}
	if (ret!=-1){
		ans=min(ans,max(ret,calc10(ret)));
		ans=min(ans,max(ret,_calc10(ret)));
		if (ret!=0){
			ans=min(ans,max(ret-1,calc10(ret-1)));
			ans=min(ans,max(ret-1,_calc10(ret-1)));
		}
	}
	l=0,r=n,ret=-1;
	while (l<=r){
		int mid=l+r>>1;
		if (calc01(mid)<=mid) ret=mid,r=mid-1;
			else l=mid+1;
	}
	if (ret!=-1){
		ans=min(ans,max(ret,calc01(ret)));
		ans=min(ans,max(ret,_calc01(ret)));
		if (ret!=0){
			ans=min(ans,max(ret-1,calc01(ret-1)));
			ans=min(ans,max(ret-1,_calc01(ret-1)));
		}
	}
	printf("%d\n",ans);
}

Measured memory_bytes: 20440