/*

Code for problem B by cookiedoth
Generated 07 Jun 2020 at 03.48 PM


──────▄▌▐▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▌
───▄▄██▌█░ВЕЗЁМ▄▀▀▀▄░ГУСЕЙ░░░░░░░
───████▌█▄███▀░◐░▄▀▀▀▄░░РАБОТЯГИ░
──██░░█▌█░░▄███▀░◐░░▄▀▀▀▄░░░░░░░
─██░░░█▌█░░░░▐░▄▀▀▀▌░░░░◐░▀███▄░
▄██████▌█▄███▀░◐░░░▌░░░░░▐░░░░░░
███████▌█░░░░▌░░░░░▌░░░░░▐░░░░░░
███████▌█▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▄▌
▀(@)▀▀▀▀▀▀▀(@)(@)▀▀▀▀▀▀▀▀▀▀▀▀▀(@)▀(@)

~_^
=_=
>_<

*/

#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#include <map>
#include <bitset>
#include <algorithm>
#include <iomanip>
#include <cmath>
#include <ctime>
#include <functional>
#include <unordered_set>
#include <unordered_map>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <complex>
#include <cassert>
#include <random>
#include <cstring>
#include <numeric>
#define ll long long
#define ld long double
#define null NULL
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define debug(a) cerr << #a << " = " << a << endl
#define forn(i, n) for (int i = 0; i < n; ++i)
#define sz(a) (int)a.size()

using namespace std;

template<class T> int chkmax(T &a, T b) {
	if (b > a) {
		a = b;
		return 1;
	}
	return 0;
}

template<class T> int chkmin(T &a, T b) {
	if (b < a) {
		a = b;
		return 1;
	}
	return 0;
}

template<class iterator> void output(iterator begin, iterator end, ostream& out = cerr) {
	while (begin != end) {
		out << (*begin) << " ";
		begin++;
	}
	out << endl;
}

template<class T> void output(T x, ostream& out = cerr) {
	output(x.begin(), x.end(), out);
}

void fast_io() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
}

struct st {
	vector<int> t, mod;
	int n;

	void build(int *a, int v, int tl, int tr) {
		if (tl == tr) {
			t[v] = a[tl];
		} else {
			int tm = (tl + tr) >> 1;
			build(a, v * 2, tl, tm);
			build(a, v * 2 + 1, tm + 1, tr);
			t[v] = max(t[v * 2], t[v * 2 + 1]);
		}
	}

	st(int *a, int _n) {
		n = _n;
		t.resize(4 * n);
		mod.resize(4 * n);
		build(a, 1, 0, n - 1);
		// output(all(t));
	}

	void add(int l, int r, int val, int v, int tl, int tr) {
		if (r < tl || tr < l) {
			return;
		}
		if (l <= tl && tr <= r) {
			mod[v] += val;
			t[v] += val;
		} else {
			int tm = (tl + tr) >> 1;
			add(l, r, val, v * 2, tl, tm);
			add(l, r, val, v * 2 + 1, tm + 1, tr);
			t[v] = max(t[v * 2], t[v * 2 + 1]) + mod[v];
		}
	}

	void add(int l, int r, int val) {
		add(l, r, val, 1, 0, n - 1);
	}

	int get_max() {
		return t[1];
	}
};

const int mx = 1e6 + 228;
string s;
int n, pref[mx];
set<int> apply_pos;

void read() {
	cin >> s;
	n = s.size();
	for (int i = 0; i < n; ++i) {
		if (s[i] == '1') {
			pref[i + 1] = pref[i] + 1;
		} else {
			pref[i + 1] = pref[i] - 1;
		}
		if (s[i] == '?') {
			apply_pos.insert(i + 1);
		}
	}
}

int r2(int x) {
	return abs(x % 2);
}

vector<pair<int, int> > vp;

void build_srt() {
	for (int i = 0; i <= n; ++i) {
		vp.emplace_back(pref[i], i);
	}
	sort(all(vp));
}

int ans;

void process(int r) {
	// cerr << "process " << r << endl;
	set<int> cur_pos = apply_pos;
	st T(pref, n + 1);
	int needed = n + 1;
	int x = vp[0].first + 1;
	if (r2(x) != r) {
		x++;
	}
	// cerr << "x = " << x << endl;
	int ptr = 0;
	while (true) {
		int old_x = x - 2;
		chkmin(ans, T.get_max() - old_x);
		while (ptr <= n && vp[ptr].first < x) {
			chkmin(needed, vp[ptr++].second);
		}
		// cerr << "needed = " << needed << endl;
		auto it = cur_pos.upper_bound(needed);
		if (it == cur_pos.begin()) {
			break;
		} else {
			int to_add = (*prev(it));
			// cerr << "to_add = " << to_add << endl;
			cur_pos.erase(to_add);
			T.add(to_add, n, 2);
		}
		x += 2;
	}
}

signed main() {
	fast_io();
	read();
	build_srt();
	ans = n;
	// cerr << "pref" << endl;
	// output(pref, pref + n + 1);
	for (int it = 0; it < 2; ++it) {
		process(it);
	}
	cout << ans << '\n';
}


Measured memory_bytes: 140976