//Awwawa! Dis cold yis ratten buy tEMMIE!
#include <bits/stdc++.h>
#define ll long long
#define maxn 1000005 /*rem*/
#define mod 998244353
#define db double
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define pi pair<int, int>
#define fi first
#define se second

template <typename T> bool chkmax(T &x,T y){return x<y?x=y,true:false;}
template <typename T> bool chkmin(T &x,T y){return x>y?x=y,true:false;}

using namespace std;
ll ksm(ll a, ll b) {
   if (!b) return 1;
   ll ns = ksm(a, b >> 1);
   ns = ns * ns % mod;
   if (b & 1) ns = ns * a % mod;
   return ns;
}
char s[maxn];
int n;
bool check(int x) {
	pi r[2] = {mp(0, x), mp(0, x)};
	for (int i = 1; i <= n; i++) {
		pi cur[2] = {mp(maxn * 10, -maxn * 10), mp(maxn * 10, -maxn * 10)};
		pi fr[2] = {r[0], r[1]};	
		for (int i = 0; i < 2; i++) {
			if (fr[i].se % 2 != i) fr[i].se--;
			if (fr[i].fi % 2 != i) fr[i].fi++;
		}
		for (int j = 0; j < 2; j++) {
			int tp = j * 2 - 1;
			if (s[i] != '0' + j) {
				for (int s = 0; s < 2; s++) {
					pi ed = mp(fr[s].fi + tp, fr[s].se + tp);
					chkmax(ed.fi, 0), 
					chkmin(ed.se, x);
					if (ed.fi > ed.se) continue;
					chkmin(cur[s ^ 1].fi, ed.fi);
					chkmax(cur[s ^ 1].se, ed.se);
				}
			} 
		}
	//	cout << i << ' ' << r[0].fi << ' ' << r[1].fi << ' ' << r[0].se << ' ' << r[1].se << endl;
		r[0] = cur[0];
		r[1] = cur[1];
		for (int i = 0; i < 2; i++) {
			if (r[i].se % 2 != i) r[i].se--;
			if (r[i].fi % 2 != i) r[i].fi++;
		}
	}
	if (r[0].fi <= r[0].se || (r[1].fi <= r[1].se)) return 1;
	return 0;
}
int main() {
	scanf("%s", s + 1);
	n = strlen(s + 1);
	int l = 0, r = n;
	check(1);
//	while (1);
	while (l < r) {
		int mid = (l + r) >> 1;
		if (check(mid)) r = mid;
		else l = mid + 1;
	}
	cout << l << endl;
	return 0;
}
