#include <bits/stdc++.h>
#define FOR(i, n) for(int i = 0; i < (n); ++i)
#define REP(i, a, b) for(int i = (a); i < (b); ++i)
#define TRAV(i, a) for(auto & i : (a))
#define SZ(x) ((int)(x).size())
#define PR std::pair
#define MP std::make_pair
#define X first
#define Y second
typedef long long ll;
typedef std::pair<int, int> PII;
typedef std::vector<int> VI;

const int INF = 1000000666;

struct Tree{
	int BOTTOM;
	VI u;
	std::vector<PII> mx, mn;
	
	void build(VI A){
		BOTTOM = 1;
		while(BOTTOM < SZ(A)) BOTTOM *= 2;
		mx.resize(BOTTOM*2, MP(-INF, 1));
		mn.resize(BOTTOM*2, MP(INF, 1));
		u.resize(BOTTOM*2);

		FOR(i, SZ(A)) mn[i+BOTTOM] = mx[i+BOTTOM] = MP(A[i], -i);
		for(int i = BOTTOM-1; i >= 1; --i){
			mn[i] = std::min(mn[i<<1], mn[(i<<1)+1]);
			mx[i] = std::max(mx[i<<1], mx[(i<<1)+1]);
		}
	}

	void upd(int v){
		mn[v].X += u[v];
		mx[v].X += u[v];
		if(v < BOTTOM){
			u[v<<1] += u[v];
			u[(v<<1)+1] += u[v];
		}
		u[v] = 0;
	}

	PII max(int a, int b, int v=1, int lo=0, int hi=-2){
		if(hi==-2) hi = BOTTOM-1;
		upd(v);
		if(a > b) return MP(-INF, 1);
		if(a == lo && b == hi){
			return mx[v];
		}
		int mid = (lo+hi)/2;
		return std::max(max(a, std::min(b, mid), v<<1, lo, mid),
						max(std::max(a, mid+1), b, (v<<1)+1, mid+1, hi));
	}

	PII min(int a, int b, int v=1, int lo=0, int hi=-2){
		if(hi==-2) hi = BOTTOM-1;
		upd(v);
		if(a > b) return MP(INF, 1);
		if(a == lo && b == hi){
			return mn[v];
		}
		int mid = (lo+hi)/2;
		return std::min(min(a, std::min(b, mid), v<<1, lo, mid),
						min(std::max(a, mid+1), b, (v<<1)+1, mid+1, hi));
	}

	void update(int a, int b, int w, int v=1, int lo=0, int hi=-2){
		if(hi == -2) hi = BOTTOM-1;
		upd(v);
		if(a > b) return;
		if(a == lo && b == hi){
			u[v] += w;
			upd(v);
			return;
		}
		int mid = (lo+hi)/2;
		update(a, std::min(b, mid), w, v<<1, lo, mid);
		update(std::max(a, mid+1), b, w, (v<<1)+1, mid+1, hi);
		mn[v] = std::min(mn[v<<1], mn[(v<<1)+1]);
		mx[v] = std::max(mx[v<<1], mx[(v<<1)+1]);
	}
};

int main(){
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);

	std::string str;
	std::cin >> str;
	int n = SZ(str);

	VI pref;
	pref.push_back(0);
	std::vector<bool> set(n+1);

	int min = 0;

	FOR(i, n){
		if(str[i] == '?'){
			set[i+1] = true;
			str[i] = '1';
		}

		if(str[i] == '1'){
			pref.push_back(pref.back()+1);
		}else{
			pref.push_back(pref.back()-1);
			min = std::min(min, pref.back());
		}
	}

	n = SZ(pref);

	auto go = [&](int can){
		VI A = pref;
		int cn = INF;
		VI tab(n);

		FOR(i, n) assert(A[i] >= can);

		for(int i = n-1; i >= 0; --i){
			int thscan = (A[i]-can)/2;
			
			tab[i] = std::min(cn, thscan);
			cn = std::min(cn, thscan);
		}

		int add = 0;
		int juz = 0;

		int mx = -INF;
		FOR(i, n){
			if(set[i] && tab[i] > juz){
				juz++;
				add += -2;
			}

			A[i] += add;
			mx = std::max(mx, A[i]);
			assert(A[i] >= can);
		}

		return mx;
	};

	int ans = std::min(go(min)-min, go(min-1)-(min-1));

	std::cout << ans << "\n";

/*
	std::cerr << str << std::endl;

	Tree tree;
	tree.build(pref);

	n = SZ(pref);
	int lastmn = tree.min(0, n-1).X;
	int ans = tree.max(0, n-1).X-tree.min(0, n-1).X;

	while(true){
		auto max = tree.max(0, n-1);

		max.Y *= -1;
		assert(max.Y != -1);

		auto it = set.upper_bound(max.Y);
		if(it == set.begin()) break;
		it--;
		
		std::cout << "chnge " << *it << std::endl;
		tree.update(*it, n-1, -2);
		set.erase(it);


		int mn = tree.min(0, n-1).X;
		int mx = tree.max(0, n-1).X;

		if(mn == lastmn - 2) break;
		lastmn = mn;

		ans = std::min(ans, mx-mn);

		std::cout << "ANS     " << mx-mn << std::endl;
	}

	std::cout << ans << "\n";
	*/

	return 0;
}

Measured memory_bytes: 16536