#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

const int MAXN = 1000010;

int suffix_one[MAXN];
int suffix_zero[MAXN];

int main() {
	string s;
	cin >> s;
	int suffix_0 = 0;
	int suffix_1 = 0;
	for (int i = s.size(); i > 0; i--) {
		suffix_one[i] = suffix_1;
		suffix_zero[i] = suffix_0;
		if (s[i - 1] == '1') {
			suffix_1++;
			suffix_0--;
		}
		else if (s[i - 1] == '0') {
			suffix_1--;
			suffix_0++;
		}
		else {
			suffix_1--;
			suffix_0--;
		}
		suffix_1 = max(suffix_1, 0);
		suffix_0 = max(suffix_0, 0);
	}
	int left = 0, right = s.size();
	while (left < right) {
		bool flag = true;
		int mid = (left + right) / 2;	
		int allowed_1 = mid;
		int allowed_0 = mid;
		for (int i = 0; flag && i < s.size(); i++) {
			if (s[i] == '1') {
				if (allowed_1 <= 0) {
					flag = false;
				}
				allowed_1--;
				allowed_0++;
			}
			else if (s[i] == '0') {
				if (allowed_0 <= 0) {
					flag = false;
				}
				allowed_1++;
				allowed_0--;
			}
			else {
				int capacity_1 = allowed_1 - suffix_one[i + 1];
				int capacity_0 = allowed_0 - suffix_zero[i + 1];
				if (allowed_1 > 0 && allowed_1 - 1 >= suffix_one[i + 1] && (capacity_1 > capacity_0 || capacity_1 == capacity_0 && allowed_1 > allowed_0)) {
					allowed_1--;
					allowed_0++;
				}
				else if (allowed_0 > 0 && allowed_0 - 1 >= suffix_zero[i + 1]) {
					allowed_1++;
					allowed_0--;
				}
				else {
					flag = false;
					break;
				}
			}
			allowed_1 = min(allowed_1, mid);
			allowed_0 = min(allowed_0, mid);
		}
		if (flag) {
			right = mid;
		}
		else {
			left = mid + 1;
		}
	}
	cout << left << endl;
}