#include <bits/stdc++.h>
#include <sys/time.h>

using namespace std;

double getTime() {
	struct timeval tv;
	gettimeofday(&tv, NULL);
	return tv.tv_sec + tv.tv_usec / 1e6;
}

const int MX = 1000001;

int val[MX], quest[MX], rev[MX];

namespace seg_tree {
	const int SIZE = 2 * MX;
	
	struct {
		int l, r;
		int lSon, rSon;
		int mn, mx, quest, rev, add;
	} t[SIZE];
	
	void recalc(int v) {
		t[v].mn = t[v].add + min(t[t[v].lSon].mn, t[t[v].rSon].mn);
		t[v].mx = t[v].add + max(t[t[v].lSon].mx, t[t[v].rSon].mx);
		t[v].quest = t[t[v].lSon].quest + t[t[v].rSon].quest;
		t[v].rev = t[t[v].lSon].rev + t[t[v].rSon].rev;
	}
	
	int tw = 0;
	int build(int l, int r) {
		int v = ++tw;
		assert(v < SIZE);
		t[v].l = l;
		t[v].r = r;
		t[v].add = 0;
		if (l < r) {
			t[v].lSon = build(l, (l + r) / 2);
			t[v].rSon = build((l + r) / 2 + 1, r);
			
			recalc(v);
		}
		else {
			t[v].mn = t[v].mx = val[l];
			t[v].quest = quest[l];
			t[v].rev = rev[l];
		}
		
		return v;
	}
	
	void flipKthQuest(int v, int k) {
		if (t[v].l == t[v].r) {
			t[v].mn += 2;
			t[v].mx += 2;
			assert(t[v].quest == 1 && k == 1);
			t[v].quest = 0;
			t[v].rev = 1;
			return;
		}
		
		if (t[t[v].lSon].quest >= k) {
			flipKthQuest(t[v].lSon, k);
			t[t[v].rSon].mn += 2;
			t[t[v].rSon].mx += 2;
			t[t[v].rSon].add += 2;
		}
		else {
			flipKthQuest(t[v].rSon, k - t[t[v].lSon].quest);
		}
		
		recalc(v);
	}
	
	void flipKthRev(int v, int k) {
		if (t[v].l == t[v].r) {
			t[v].mn -= 2;
			t[v].mx -= 2;
			assert(t[v].rev == 1 && k == 1);
			t[v].quest = 1;
			t[v].rev = 0;
			return;
		}
		
		if (t[t[v].lSon].rev >= k) {
			flipKthRev(t[v].lSon, k);
			t[t[v].rSon].mn -= 2;
			t[t[v].rSon].mx -= 2;
			t[t[v].rSon].add -= 2;
		}
		else {
			flipKthRev(t[v].rSon, k - t[t[v].lSon].rev);
		}
		
		recalc(v);
	}
	
	pair<int, int> countBeforeMin(int v) {
		if (t[v].l == t[v].r) return {t[v].quest, t[v].rev};
		
		if (t[t[v].lSon].mn + t[v].add == t[v].mn) {
			return countBeforeMin(t[v].lSon);
		}
		else {
			assert(t[t[v].rSon].mn + t[v].add == t[v].mn);
			
			auto res = countBeforeMin(t[v].rSon);
			res.first += t[t[v].lSon].quest;
			res.second += t[t[v].lSon].rev;
			return res;
		}
	}
}

char s[MX + 1];

int suffmax[MX + 1], x[MX];

int main() {
	double startTime = getTime();
	
	ignore = scanf("%s", s);
	
	int n = strlen(s);
	
	suffmax[n] = 0;
	for (int i = n - 1; i >= 0; i--) {
		if (s[i] == '1') suffmax[i] = suffmax[i + 1] + 1;
		else suffmax[i] = max(0, suffmax[i + 1] - 1);
	}
	
	int mx = suffmax[0];
	for (int i = 0, cur = 0; i < n; i++) {
		if (s[i] == '?') {
			if (cur + 1 + suffmax[i + 1] <= mx) {
				x[i] = 1;
			}
			else {
				x[i] = -1;
			}
		}
		else {
			x[i] = s[i] == '0' ? -1 : 1;
		}
		
		cur += x[i];
	}
	
	val[0] = 0;
	for (int i = 0; i < n; i++) {
		val[i + 1] = val[i] + x[i];
		if (s[i] == '?') {
			if (x[i] == -1) quest[i + 1] = 1;
			else rev[i + 1] = 1;
		}
	}
	
	int root = seg_tree::build(0, n);
	
	int ans = seg_tree::t[root].mx - seg_tree::t[root].mn;
	int it = 0;
	while (true) {
		int q, r;
		tie(q, r) = seg_tree::countBeforeMin(root);
		if (q == 0) break;
		
		if (r < seg_tree::t[root].rev) {
			seg_tree::flipKthRev(root, r + 1);
		}
		
		seg_tree::flipKthQuest(root, q);
		
		ans = min(seg_tree::t[root].mx - seg_tree::t[root].mn, ans);
		
		it++;
		if (it == 1000) {
			it = 0;
			if (getTime() - startTime > 1.9) break;
		}
	}
	
	printf("%d\n", ans);
	
	return 0;
}


Measured memory_bytes: 94648