#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
    #define eprintf(...) fprintf(stderr, __VA_ARGS__)
#else
    #define eprintf(...) 42
#endif

using ll = long long;
using ld = long double;
using D = double;
using uint = unsigned int;
template<typename T>
using pair2 = pair<T, T>;
using pii = pair<int, int>;
using pli = pair<ll, int>;
using pll = pair<ll, ll>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second

const int maxn = 1000006;

char s[maxn];
int n;

bool can(int mxb)
{
	//cout << "can " << mxb << endl;
	for (int par = 0; par < 2; par++)
	{
		int low = par;
		int high = (mxb % 2 == par ? mxb : mxb - 1);
		if (low > high) continue;
		assert(low % 2 == high % 2);
		bool ok = true;
		for (int i = 0; i < n; i++)
		{
			if (s[i] == '0')
			{
				if (low == 0) low = 1;
				else low--;
				high--;
			} else if (s[i] == '1')
			{
				if (high == mxb) high = mxb - 1;
				else high++;
				low++;
			} else if (s[i] == '?')
			{
				if (low == 0) low = 1;
				else low--;
				if (high == mxb) high = mxb - 1;
				else high++;
			} else assert(false);
			//cout << i << ' ' << low << ' ' << high << endl;
			if (low > high)
			{
				ok = false;
				break;
			}
		}
		if (ok) return true;
	}
	return false;
}

int main()
{
	scanf("%s", s);
	n = strlen(s);
	int l = 0;
	int r = n;
	while (r - l > 1)
	{
		int m = (l + r) / 2;
		if (can(m)) r = m;
		else l = m;
	}
	printf("%d\n", r);
    return 0;
}
