#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
const int N=1000005,M=1000000007;
int n,i,j,ans,l,r,al,ar,sp;
char c[N];
void rt(int m,int l,int r)
{
	for(i=strlen(c+1);i>=1;--i)
	{
		if(c[i]=='0')
		{
			--l;
			--r;
			if(l<0)
				l+=2;
		}
		if(c[i]=='1')
		{
			++l,++r;
			if(r>m)
				r-=2;
		}
		if(c[i]=='?')
		{
			--l;
			if(l<0)
				l+=2;
			++r;
			if(r>m)
				r-=2;
		}
		if(l>r||l>m||r<0)
		{
			al=1;
			ar=0;
			return;
		}
	}
	al=l,ar=r;
}
bool check(int m)
{
	int i;
	int a[2][2],b[2][2];
	rt(m,0,m/2*2);
	a[0][0]=al,a[0][1]=ar;
	rt(m,1,(m&1?m:m-1));
	a[1][0]=al,a[1][1]=ar;
	for(i=1;c[i];++i)
		if(c[i]=='0')
			c[i]='1';
		else
			if(c[i]=='1')
				c[i]='0';
	rt(m,0,m/2*2);
	b[0][0]=m-ar,b[0][1]=m-al;
	rt(m,1,(m&1?m:m-1));
	b[1][0]=m-ar,b[1][1]=m-al;
	if(m&1)
	{
		swap(b[0][0],b[1][0]);
		swap(b[0][1],b[1][1]);
	}
	for(i=1;c[i];++i)
		if(c[i]=='0')
			c[i]='1';
		else
			if(c[i]=='1')
				c[i]='0';
	if(min(a[0][1],b[0][1])>=max(a[0][0],b[0][0])||min(a[1][1],b[1][1])>=max(a[1][0],b[1][0]))
		return true;
	else
		return false;
}
int main()
{
	scanf("%s",c+1);
	int l=1,r=strlen(c+1);
	while(l<r)
	{
		int mid=l+r>>1;
		if(check(mid))
			r=mid;
		else
			l=mid+1;
	}
	cout<<l;
}
