#include <bits/stdc++.h>

#define SZ(x) (((int)x.size()))
#define all(x) (x).begin(), (x).end()
#define pb push_back

typedef long long ll;
typedef long double ld;

using namespace std;

const int maxn = 1*1000*1000+10;
string s;
vector<pair<int, pair<int, int>>> vec;
vector<int> qm;
bool b;
int L[2], R[2], l, r, mid, mn, mx;
char c[maxn];

bool ok(int x)
{
    L[0] = 0;
    R[0] = x / 2 * 2 + 2;
    L[1] = 1;
    if (x & 1)
        R[1] = x + 2;
    else
        R[1] = x + 1;
    //cerr << "init: " << L[0] << " " << R[0] << " " << L[1] << " " << R[1] << endl;
    for (int i = SZ(vec) - 1; i >= 0; i--)
    {
        //cerr << "i: " << i << endl;
        for (int j = 0; j < 2; j++)
        {
            L[j] -= vec[i].first;
            R[j] -= vec[i].first;
        }
        if (vec[i].first & 1)
        {
            swap(L[0], L[1]);
            swap(R[0], R[1]);
        }
        L[0] = max(L[0], 0);
        R[0] = min(R[0], x / 2 * 2 + 2);
        L[1] = max(L[1], 1);
        if (x & 1)
            R[1] = min(R[1], x + 2);
        else
            R[1] = min(R[1], x + 1);
        //cerr << "in the beginning: " << L[0] << " " << R[0] << " " << L[1] << " " << R[1] << endl;
        mn = vec[i].second.first;
        mx = vec[i].second.second;
        //cerr << "mn & mx: " << mn << " " << mx << endl;
        if ((-mn) & 1)
        {
            if ((x - mx) & 1)
            {
                L[0] = max(L[0], -mn + 1);
                L[1] = max(L[1], -mn);
                R[0] = min(R[0], x - mx + 1);
                R[1] = min(R[1], x - mx + 2);
            }
            else
            {
                L[0] = max(L[0], -mn + 1);
                L[1] = max(L[1], -mn);
                R[0] = min(R[0], x - mx + 2);
                R[1] = min(R[1], x - mx + 1);
            }
        }
        else
        {
            if ((x - mx) & 1)
            {
                L[0] = max(L[0], -mn);
                L[1] = max(L[1], -mn + 1);
                R[0] = min(R[0], x - mx + 1);
                R[1] = min(R[1], x - mx + 2);
            }
            else
            {
                L[0] = max(L[0], -mn);
                L[1] = max(L[1], -mn + 1);
                R[0] = min(R[0], x - mx + 2);
                R[1] = min(R[1], x - mx + 1);
            }
        }
        //cerr << "in the beginning 2: " << L[0] << " " << R[0] << " " << L[1] << " " << R[1] << endl;
        for (int j = 0; j < 2; j++)
        {
            if (L[j] < R[j])
            {
                L[j] -= qm[i];
                R[j] += qm[i];
            }
        }
        if (qm[i] & 1)
        {
            swap(L[0], L[1]);
            swap(R[0], R[1]);
        }
        L[0] = max(L[0], 0);
        R[0] = min(R[0], x / 2 * 2 + 2);
        L[1] = max(L[1], 1);
        if (x & 1)
            R[1] = min(R[1], x + 2);
        else
            R[1] = min(R[1], x + 1);
        //cerr << "final: " << L[0] << " " << R[0] << " " << L[1] << " " << R[1] << endl;
    }
    if (R[0] > L[0] || R[1] > L[1])
        return 1;
    return 0;
}

int main()
{
    ios::sync_with_stdio(0);
    scanf("%s", c);
    s = c;
    for (int i = SZ(s) - 1; i >= 0; i--)
    {
        if (s[i] != '?')
        {
            s = s.substr(0, i + 1);
            break;
        }
    }
    if (s[SZ(s) - 1] == '?')
    {
        printf("1");
        return 0;
    }
    b = 1;
    for (int i = 0; i < SZ(s); i++)
    {
        if (s[i] != '?' && b)
        {
            b = 0;
            qm.pb(i - l);
        }
        if (s[i] == '?' && !b)
        {
            b = 1;
            l = i;
        }
    }
    s += "?";
    b = 0;
    for (int i = 0; i < SZ(s); i++)
    {
        if (s[i] != '?' && !b)
        {
            b = 1;
            l = mn = mx = 0;
        }
        if (s[i] == '?' && b)
        {
            b = 0;
            vec.pb({l, {mn, mx}});
            mid = max(mid, mx - mn);
        }
        if (s[i] == '0')
        {
            l--;
            mn = min(mn, l);
            mx = max(mx, l);
        }
        if (s[i] == '1')
        {
            l++;
            mn = min(mn, l);
            mx = max(mx, l);
        }
    }
    l = mid - 1;
    r = SZ(s);
    while (r - l > 1)
    {
        mid = (l + r) / 2;
        if (ok(mid))
            r = mid;
        else
            l = mid;
    }
    printf("%d", r);
	return 0;
}


Measured memory_bytes: 14944