// #pragma GCC target("avx")  // CPU 処理並列化
// #pragma GCC optimize("O3")  // CPU 処理並列化
// #pragma GCC optimize("unroll-loops")  // 条件処理の呼び出しを減らす
// #define BEGIN_STACK_EXTEND(size) void * stack_extend_memory_ = malloc(size);void * stack_extend_origin_memory_;char * stack_extend_dummy_memory_ = (char*)alloca((1+(int)(((long long)stack_extend_memory_)&127))*16);*stack_extend_dummy_memory_ = 0;asm volatile("mov %%rsp, %%rbx\nmov %%rax, %%rsp":"=b"(stack_extend_origin_memory_):"a"((char*)stack_extend_memory_+(size)-1024));
// #define END_STACK_EXTEND asm volatile("mov %%rax, %%rsp"::"a"(stack_extend_origin_memory_));free(stack_extend_memory_);

#include<stdio.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<string.h>
#include<vector>
#include<set>
#include<map>
#include<bitset>
#include<stdlib.h>
#include<cassert>
#include<time.h>
#include<bitset>
#include<numeric>
#include<unordered_set>
#include<unordered_map>
#include<complex>
using namespace std;
const long long mod=1000000007;
const long long inf=mod*mod;
const long long d2=(mod+1)/2;
const double EPS=1e-11;
const double INF=1e+10;
const double PI=acos(-1.0);
const int C_SIZE = 3100000;
const int UF_SIZE = 3100000;
namespace{
	long long fact[C_SIZE];
	long long finv[C_SIZE];
	long long inv[C_SIZE];
	inline long long Comb(int a,int b){
	 	if(a<b||b<0)return 0;
	 	return fact[a]*finv[b]%mod*finv[a-b]%mod;
	}
	void init_C(int n){
		fact[0]=finv[0]=inv[1]=1;
		for(int i=2;i<n;i++){
			inv[i]=(mod-(mod/i)*inv[mod%i]%mod)%mod;
		}
		for(int i=1;i<n;i++){
			fact[i]=fact[i-1]*i%mod;
			finv[i]=finv[i-1]*inv[i]%mod;
		}
	}
	long long pw(long long a,long long b){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%mod;
			a=a*a%mod;
			b/=2;
		}
		return ret;
	}
	long long pw_mod(long long a,long long b,long long M){
		if(a<0LL)return 0;
		if(b<0LL)return 0;
		long long ret=1;
		while(b){
			if(b%2)ret=ret*a%M;
			a=a*a%M;
			b/=2;
		}
		return ret;
	}
	int pw_mod_int(int a,int b,int M){
		if(a<0)return 0;
		if(b<0)return 0;
		int ret=1;
		while(b){
			if(b%2)ret=(long long)ret*a%M;
			a=(long long)a*a%M;
			b/=2;
		}
		return ret;
	}
	int ABS(int a){return max(a,-a);}
	long long ABS(long long a){return max(a,-a);}
	double ABS(double a){return max(a,-a);}
	int sig(double r) { return (r < -EPS) ? -1 : (r > +EPS) ? +1 : 0; }
	int UF[UF_SIZE];
	void init_UF(int n){
		for(int i=0;i<n;i++)UF[i]=-1;
	}
	int FIND(int a){
		if(UF[a]<0)return a;
		return UF[a]=FIND(UF[a]);
	}
	void UNION(int a,int b){
		a=FIND(a);b=FIND(b);if(a==b)return;
		if(UF[a]>UF[b])swap(a,b);
		UF[a]+=UF[b];UF[b]=a;
	}
}
// ここから編集しろ
char in[1100000];
pair<int,int>segtree[3][1<<21];
void add(int a,int b,int c,int d,int e,int f){
	if(d<a||b<c)return ;
	if(c<=a&&b<=d){
		segtree[0][e].first+=f;
		segtree[1][e].first+=f;
		segtree[2][e].first+=f;
		return;
	}else{
		add(a,(a+b)/2,c,d,e*2,f);
		add((a+b)/2+1,b,c,d,e*2+1,f);
	}
	pair<int,int> t=min(segtree[0][e*2],segtree[0][e*2+1]);
	segtree[0][e].second=t.second;
	segtree[0][e].first+=t.first;
	segtree[0][e*2].first-=t.first;
	segtree[0][e*2+1].first-=t.first;

	t=min(segtree[1][e*2],segtree[1][e*2+1]);
	segtree[1][e].second=t.second;
	segtree[1][e].first+=t.first;
	segtree[1][e*2].first-=t.first;
	segtree[1][e*2+1].first-=t.first;
	
	t=max(segtree[2][e*2],segtree[2][e*2+1]);
	segtree[2][e].second=t.second;
	segtree[2][e].first+=t.first;
	segtree[2][e*2].first-=t.first;
	segtree[2][e*2+1].first-=t.first;
}
int p[1100000];
set<int>S0;
set<int>S1;
int SZ=(1<<20);
int main(){
	scanf("%s",in);

	int n=strlen(in);
	for(int i=0;i<n;i++){
		if(in[i]=='0')in[i]='1';
		else if(in[i]=='1')in[i]='0';
	}
	for(int i=0;i<=n;i++){
		segtree[0][SZ+i]=make_pair(0,i);
		segtree[1][SZ+i]=make_pair(0,-i);
		segtree[2][SZ+i]=make_pair(0,i);
	}
	for(int i=SZ-1;i>0;i--){
		segtree[0][i]=min(segtree[0][i*2],segtree[0][i*2+1]);
		segtree[1][i]=min(segtree[1][i*2],segtree[1][i*2+1]);
		segtree[2][i]=max(segtree[2][i*2],segtree[2][i*2+1]);
	}
	int tmp=0;
	for(int i=0;i<n;i++){
		if(in[i]=='1'){
			tmp++;
		}else if(in[i]=='?'){
			S0.insert(i);
			tmp--;
		}else tmp--;
		add(0,SZ-1,i+1,i+1,1,tmp);
	}
	int ret=mod;
	int CNT=0;
	while(1){
		CNT++;
		pair<int,int>L=segtree[0][1];
		pair<int,int>R=segtree[1][1];
		pair<int,int>H=segtree[2][1];
		ret=min(ret,H.first-L.first);

		int pl=L.second;
		int pr=-R.second;

		set<int>::iterator it=S0.lower_bound(pl);
		if(it==S0.begin())break;
		it--;
		if(CNT<11000)pr=pl;
		set<int>::iterator it2=S1.lower_bound(pr);

		int aL=1+(*it);
		int aR=n;
		if(it2!=S1.end()){
			aR=*it2;
		}
		if(pl<=H.second&&H.second<=pr){
			set<int>::iterator it3=S1.lower_bound(H.second);
			if(it3!=S1.begin()){
				it3--;
				if((*it3)>=pl){
					aR=*it3;
					it2=it3;
				}
			}

			// pr=pl;
		}
		// printf("%d %d %d, %d %d\n",L.first,R.first,H.first,aL,aR);
		add(0,SZ-1,aL,aR,1,2);
		int f=*it;
		int g=-1;
		if(it2!=S1.end())g=*it2;
		S0.erase(f);
		S1.insert(f);

		if(g!=-1){
			S1.erase(g);
			S0.insert(g);
		}
	}
	printf("%d\n",ret);
}

Measured memory_bytes: 99168