#include <iostream>
#include <cstdio>
#include <cstring>

char s[1010000]; int n;

bool check(int len)
{
	int l = -len, r = 0;
	int type = 1;
	for(int i = n; i >= 1; i--)
	{
		if(s[i] == '0')
		{
			if(r + len == 0) return 0;
			else
			{
				r--;
				if(l + len == 0) l += type; l--;
			}
		}
		if(s[i] == '1')
		{
			if(l == 0) return 0;
			else
			{
				l++;
				if(r == 0) r -= type; r++;
			}
		}
		if(s[i] == '?')
		{
			if(l == r)
			{
				if(l == 0) l--, r--;
				else if(l + len == 0) l++, r++;
				else
				{
					type = 2;
					l--; r++;
				}
			}
			else
			{
				if(l + len == 0) l += type; l--;
				if(r == 0) r -= type; r++;
			}
		}
	}
	return 1;
}

int main()
{
	scanf("%s", s + 1);
	n = strlen(s + 1);
	int l = 1, r = n + 1;
	while(l < r)
	{
		int mid = l + r >> 1;
		if(check(mid)) r = mid;
		else l = mid + 1;
	}
	printf("%d\n", r);
}