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

template<typename Type> class RangeAddMinSegmentTree {
private:
	unsigned size_; std::vector<Type> dat1, dat2;
	inline void update_(unsigned a, unsigned b, Type x, unsigned k, unsigned l, unsigned r) {
		if (r <= a || b <= l) return;
		if (a <= l && r <= b) {
			dat2[k] += x; return;
		}
		update_(a, b, x, (k << 1), l, (l + r) >> 1);
		update_(a, b, x, (k << 1) + 1, (l + r) >> 1, r);
		dat1[k] = std::min(dat1[k << 1] + dat2[k << 1], dat1[(k << 1) + 1] + dat2[(k << 1) + 1]);
	}
	inline Type query_(unsigned a, unsigned b, unsigned k, unsigned l, unsigned r) {
		if (r <= a || b <= l) return std::numeric_limits<Type>::max();
		if (a <= l && r <= b) return dat1[k] + dat2[k];
		Type lc = query_(a, b, (k << 1), l, (l + r) >> 1);
		Type rc = query_(a, b, (k << 1) + 1, (l + r) >> 1, r);
		return std::min(lc, rc) + dat2[k];
	}
public:
	RangeAddMinSegmentTree() : size_(0), dat1(std::vector<Type>()), dat2(std::vector<Type>()) {};
	RangeAddMinSegmentTree(int size__) {
		for (size_ = 1; size_ < size__; ) size_ <<= 1;
		dat1.resize(size_ << 1, 0);
		dat2.resize(size_ << 1, 0);
	}
	inline unsigned size() { return size_; }
	inline void add(unsigned i, Type x) {
		update_(i, i + 1, x, 1, 0, size_);
	}
	inline void add(unsigned l, unsigned r, Type x) {
		update_(l, r, x, 1, 0, size_);
	}
	inline Type query(unsigned l, unsigned r) {
		return query_(l, r, 1, 0, size_);
	}
};

string S;
int Base[1 << 20], BaseUp[1 << 20];
int Answer = (1 << 30);
RangeAddMinSegmentTree<int> Z1, Z2;

int main() {
	cin >> S;
	Z1 = RangeAddMinSegmentTree<int>(S.size() + 2);
	Z2 = RangeAddMinSegmentTree<int>(S.size() + 2);

	// 基本高さを求める
	for (int i = 0; i < S.size(); i++) {
		if (S[i] == '0' || S[i] == '?') Base[i + 1] = Base[i] - 1;
		else Base[i + 1] = Base[i] + 1;
	}
	BaseUp[S.size()] = Base[S.size()];
	for (int i = S.size() - 1; i >= 0; i--) BaseUp[i] = max(BaseUp[i + 1], Base[i]);
	int BaseMax = 0;
	for (int i = 0; i <= S.size(); i++) BaseMax = max(BaseMax, Base[i]);

	// 最大高さ偶数の場合
	int CurMax = BaseMax; if (CurMax % 2 == 1) CurMax += 1;
	int CurDep = 0; vector<int> vec;
	for (int i = 0; i < S.size(); i++) {
		Z1.add(i, CurDep);
		if (S[i] == '0') CurDep--;
		if (S[i] == '1') CurDep++;
		if (S[i] == '?') {
			int ExpHeight = CurDep + 1 + (BaseUp[i + 1] - Base[i + 1]);
			if (ExpHeight > CurMax) { vec.push_back(i); CurDep--; }
			else { CurDep++; }
		}
	}
	Z1.add(S.size(), CurDep);
	for (int i = 0; i <= vec.size(); i++) {
		int UpHeight = CurMax + i * 2;
		int DownHeight = Z1.query(0, S.size() + 1);
		Answer = min(Answer, UpHeight - DownHeight);
		if (i != vec.size()) { Z1.add(vec[i] + 1, S.size() + 1, 2); }
	}

	// 最大高さ奇数の場合
	CurMax = BaseMax; if (CurMax % 2 == 0) CurMax += 1;
	CurDep = 0; vector<int> vec2;
	for (int i = 0; i < S.size(); i++) {
		Z2.add(i, CurDep);
		if (S[i] == '0') CurDep--;
		if (S[i] == '1') CurDep++;
		if (S[i] == '?') {
			int ExpHeight = CurDep + 1 + (BaseUp[i + 1] - Base[i + 1]);
			if (ExpHeight > CurMax) { vec2.push_back(i); CurDep--; }
			else { CurDep++; }
		}
	}
	Z2.add(S.size(), CurDep);
	for (int i = 0; i <= vec2.size(); i++) {
		int UpHeight = CurMax + i * 2;
		int DownHeight = Z2.query(0, S.size() + 1);
		Answer = min(Answer, UpHeight - DownHeight);
		if (i != vec2.size()) { Z2.add(vec2[i] + 1, S.size() + 1, 2); }
	}

	// 答えを出力
	cout << Answer << endl;
	return 0;
}

Measured memory_bytes: 49964