//~ while (clock()<=69*CLOCKS_PER_SEC)
//~ #pragma comment(linker, "/stack:200000000")
#ifndef LOCAL
#pragma GCC optimize("O3")
#endif
//~ #pragma GCC optimize("Ofast")
//~ #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//~ #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define st first
#define nd second

using namespace __gnu_pbds;
using namespace std;
 
template <typename T>
using ordered_set =
	tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
	*this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
 
#define shandom_ruffle random_shuffle
 
using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using vi=vector<int>;
using vll=vector<ll>;

struct SegTree {
	struct Node {
		int push;
		int maxval;

		Node() : push(0), maxval(0) {};

		Node Merge(const Node &rhs) const {
			Node ans;
			ans.maxval = max(maxval, rhs.maxval);
			return ans;
		}
	};

	vector<Node> nodes;
	int base;

	SegTree(int n) : base(1) {
		while (base < n + 1) { base *= 2; }
		nodes.resize(base * 2);
		for (int i = base-1; i >= 0; --i) {
			nodes[i] = nodes[i*2].Merge(nodes[i*2+1]);
		}
	}

	int lv, rv, valv;

	void Touch(int v) {
		if (v < base) {
			for (int s : {v*2, v*2+1}) {
				nodes[s].maxval += nodes[v].push;
				nodes[s].push += nodes[v].push;
			}
		}
		nodes[v].push = 0;
	}

	void AddValRec(int lbase, int rbase, int v) {
		if (lbase >= rv || rbase <= lv) { return; }
		Touch(v);
		if (lv <= lbase && rbase <= rv) {
			nodes[v].maxval += valv;
			nodes[v].push += valv;
			return;
		}

		const int mid = (lbase + rbase) / 2;
		AddValRec(lbase, mid, v*2);
		AddValRec(mid, rbase, v*2+1);
		nodes[v] = nodes[v*2].Merge(nodes[v*2+1]);
	}

	void AddVal(int L, int R, int val) {
		lv = L; rv = R; valv = val;
		return AddValRec(0, base, 1);
	}
};

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(11);
	cerr << fixed << setprecision(6);

	string s;
	cin >> s;
	int n = SZ(s);

	int mx = 0, cur = 0;
	for (char ch : s) {
		cur += (ch == '1' ? 1 : -1);
		mx = max(mx, cur);
	}
	int ans = 1e9;

	for (int iter = 0; iter <= 1; ++iter) {
		SegTree tree(n + 2);
		for (int i = 0; i < n; ++i) {
			tree.AddVal(i + 1, n + 1, s[i] == '1' ? 1 : -1);
		}

		int cur = 0;
		int mnval = 0;

		for (int i = 0; i < n; ++i) {
			if (s[i] == '?') {
				tree.AddVal(i + 1, n + 1, +2);
				if (tree.nodes[1].maxval > mx) {
					tree.AddVal(i + 1, n + 1, -2);
					cur -= 1;
				} else {
					cur += 1;
				}
			} else {
				cur += (s[i] == '0' ? -1 : 1);
			}
			mnval = min(mnval, cur);
		}
		
		ans = min(ans, tree.nodes[1].maxval - mnval);
		++mx;
	}

	cout << ans << "\n";
}


Measured memory_bytes: 20652