#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;

int gi() {
	int x=0,o=1;char ch=getchar();
	while(!isdigit(ch)&&ch!='-') ch=getchar();
	if(ch=='-') o=-1,ch=getchar();
	while(isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	return x*o;
}

int n,mid;
char s[N];

struct dat {
	int l,r;
	dat() {}
	dat(int _l,int _r) {
		l=_l;r=_r;
		if(l<0) l+=2;
		if(r>mid) r-=2;
	}
	bool empty() {
		return l>r;
	}
} I[2],new_I[2];

bool check() {
	I[0]=dat(0,mid-(mid&1));
	I[1]=dat(1,mid-(mid&1^1));
	//cerr<<I[1].l<<' '<<I[1].r<<'\n';
	for(int i=1;i<=n;i++) {
		if(s[i]=='1') {
			new_I[0]=dat(I[1].l+1,I[1].r+1);
			new_I[1]=dat(I[0].l+1,I[0].r+1);
		}
		else if(s[i]=='0') {
			new_I[0]=dat(I[1].l-1,I[1].r-1);
			new_I[1]=dat(I[0].l-1,I[0].r-1);
		}
		else {
			new_I[0]=dat(I[1].l-1,I[1].r+1);
			new_I[1]=dat(I[0].l-1,I[0].r+1);
		}
		if(I[0].empty()) new_I[1]=dat(1,0);
		if(I[1].empty()) new_I[0]=dat(1,0);
		I[0]=new_I[0];I[1]=new_I[1];
		//cerr<<I[0].l<<' '<<I[0].r<<' '<<I[1].l<<' '<<I[1].r<<'\n';
		if(I[0].empty()&&I[1].empty()) return 0;
	}
	return 1;
}

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