#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <set>
#include <map>
#include <vector>
#include <string>

#include <cmath>
#include <queue>
#include <stack>

using namespace std;

string getStr() {
	string res = "";
	char c = getchar();
	while (c == '0' || c == '1' || c == '?') {
		res.push_back(c);
		c = getchar();
	}
	return res;
}

string s;
int n;

vector<int> maxFrom, maxTo, minFrom, minTo;
vector<int> a;

void input() {
	s = getStr();
	string t;
	n = s.length();
	maxFrom = vector<int>(n + 1, 0);
	minFrom = vector<int>(n + 1, 0);

	// maxFrom: start from k, set all ? to be -1, get the maximum of sum
	// minFrom: start from k, set all ? to be 1, get the minimum of sum

	minFrom[n] = maxFrom[n] = 0;
	for (int i = n - 1; i >= 0; --i) {
		int sForMin, sForMax;
		switch (s[i]) {
			case '?': { sForMin = 1; sForMax = -1; break;}
			case '0': { sForMin = sForMax = -1; break;}
			case '1': { sForMin = sForMax = 1; break;}
		}
		minFrom[i] = min(0, minFrom[i + 1] + sForMin);
		maxFrom[i] = max(0, maxFrom[i + 1] + sForMax);
	}
	int ans = n;
	int Z = maxFrom[0];
	for (int M = Z; M < Z + 2; ++M) {
		t = s;
		int nowVal = 0, nowMax = 0, nowMin = 0;
		for (int i = 0; i < n; ++i) {
			if (s[i] == '?') {
				int newMax = max(nowVal + 1 + maxFrom[i + 1], nowMax);
				if (newMax > M) { 
					t[i] = '0';
					nowVal -= 1;
				} else {
					t[i] = '1';
					nowVal += 1;
				}
			} else {
				nowVal += (s[i] == '0') ? (-1) : 1;
			}
			nowMax = max(nowMax, nowVal + maxFrom[i + 1]);
		}

		// cout << t << endl;

		nowMax = 0;
		nowMin = 0;
		nowVal = 0;
		for (int i = 0; i < n; ++i) {
			nowVal += ((t[i] == '1') ? 1 : -1);
			nowMax = max(nowVal, nowMax);
			nowMin = min(nowVal, nowMin);
		}
		ans = min(ans, nowMax - nowMin);
	}
	// int qN = 10;
	// for (int q = 0; q < qN; ++q) {

	// 	t = s;

	// 	int nowVal = 0, nowMin = 0, nowMax = 0;
	// 	for (int i = 0; i < n; ++i) {
	// 		// ans = max(ans, max(nowMax, nowVal + maxFrom[i]) - min(nowMin, nowVal + minFrom[i]));
	// 		// ans = max(ans, nowMax - nowMin);

	// 		if (s[i] != '?') {
	// 			nowVal += ((s[i] == '0') ? -1 : 1);
	// 		} else {
	// 			int oldMin = min(nowMin, nowVal + minFrom[i]);
	// 			int newMin = min(nowVal - 1 + minFrom[i + 1], nowMin);
	// 			int oldMax = max(nowMax, nowVal + maxFrom[i]);
	// 			int newMax = max(nowVal + 1 + maxFrom[i + 1], nowMax);

	// 			if (q == 0) {
	// 				if (newMin < oldMin) {
	// 					nowVal += 1;
	// 					t[i] = '1';
	// 				} else {
	// 					nowVal -= 1;
	// 					t[i] = '0';
	// 				}
	// 			}

	// 			else if (q == qN - 1) {
	// 				if (newMax > oldMax) {
	// 					nowVal -= 1;
	// 					t[i] = '0';
	// 				} else {
	// 					nowVal += 1;
	// 					t[i] = '1';
	// 				}
	// 			}

	// 			else {
	// 				if (newMin < oldMin) {
	// 					nowVal += 1;
	// 					t[i] = '1';
	// 				} else if (newMax > oldMax) {
	// 					nowVal -= 1;
	// 					t[i] = '0';
	// 				} else {
	// 					int choice = rand() % 2;
	// 					if (q == 0) {
	// 						choice = 0;
	// 					}
	// 					if (q == qN - 1) {
	// 						choice = 1;
	// 					}
	// 					nowVal += ((choice) ? 1 : (-1));
	// 					t[i] = '0' + choice;
	// 				}
	// 			}
	// 		}

	// 		nowMin = min(nowMin, nowVal + minFrom[i + 1]);
	// 		nowMax = max(nowMax, nowVal + maxFrom[i + 1]);
	// 	}

	// 	nowMax = 0;
	// 	nowMin = 0;
	// 	nowVal = 0;
	// 	for (int i = 0; i < n; ++i) {
	// 		nowVal += ((t[i] == '1') ? 1 : -1);
	// 		nowMax = max(nowVal, nowMax);
	// 		nowMin = min(nowVal, nowMin);
	// 	}
	// 	// ans = max(ans, nowMax - nowMin);
	// 	if (q == 0) {
	// 		ans = nowMax - nowMin;
	// 	} else {
	// 		ans = min(ans, nowMax - nowMin);
	// 	}
	// }

	// t = s;
	// // cout << t << endl;
	// nowVal = 0;
	// nowMin = 0;
	// nowMax = 0;

	// for (int i = 0; i < n; ++i) {
	// 	// ans = max(ans, max(nowMax, nowVal + maxFrom[i]) - min(nowMin, nowVal + minFrom[i]));
	// 	// ans = max(ans, nowMax - nowMin);

	// 	if (s[i] != '?') {
	// 		nowVal += ((s[i] == '0') ? -1 : 1);
	// 	} else {
	// 		int oldMax = max(nowMax, nowVal + maxFrom[i]);
	// 		int newMax = max(nowVal + 1 + maxFrom[i + 1], nowMax);
	// 		if (newMax > oldMax) {
	// 			nowVal -= 1;
	// 			t[i] = '0';
	// 		} else {
	// 			nowVal += 1;
	// 			t[i] = '1';
	// 		}
	// 	}

	// 	nowMin = min(nowMin, nowVal);
	// 	nowMax = max(nowMax, nowVal);
	// }

	// nowMax = 0;
	// nowMin = 0;
	// nowVal = 0;
	// for (int i = 0; i < n; ++i) {
	// 	nowVal += ((t[i] == '1') ? 1 : -1);
	// 	nowMax = max(nowVal, nowMax);
	// 	nowMin = min(nowVal, nowMin);
	// }
	// // ans = max(ans, nowMax - nowMin);
	// ans = min(ans, nowMax - nowMin);


	// maxTo = vector<int>(n, 0);
	// minTo = vector<int>(n, 0);

	// a = vector<int>(n);
	// for (int i = 0; i < n; ++i) {
	// 	if (s[i] == '0') {
	// 		a[i] = 1;
	// 	} else {
	// 		a[i] = -1;
	// 	}
	// }
	// int maxSum = 0, minSum = 0, sum = 0;
	// for (int i = 0; i < n; ++i) {
	// 	sum += a[i];
	// 	maxSum = max(sum, maxSum);
	// 	minSum = min(sum, minSum);
	// 	maxTo[i] = maxSum;
	// 	minTo[i] = minSum;
	// }

	// maxSum = 0; minSum = 0; sum = 0;
	// for (int i = n - 1; i >= 0; --i) {
	// 	sum += a[i];
	// 	maxSum
	// }
	std::cout << ans << endl;
}

int main() {
	input();
	return 0;
}

Measured memory_bytes: 13160