
"""

https://atcoder.jp/contests/agc045/tasks/agc045_b

交互が最高
アンバランス度の定義を変えたい
1の数 = 区間和
0の数 = 区間長さ-1の数
アンバランス度 = abs(区間長さ - 区間和 * 2)
→ abs( r-l+1 - (dp[r]-dp[l])*2 )
  =abs( r-dp[r]*2 - (l-dp[l]*2) + 1 )

アンバランス度は2分探索すればよさそう
あとは、アンバランス度x以下を達成できるか？
の判定問題

連続してxこ並ぶ場所があると不可能
アンバランス度は、 (l-dp[l]*2) の最大・最小値さえ持っておけば計算できる
x以下を達成する方法は？

始めて?が来た時を考える
今までの (l-dp[l]*2) の最大・最小値 は持っている
なるべく最大・最小値は更新しない方がいい
1にする→1減らす
0にする→1増やす

1増やす・1減らすを選んで差を x-1以下にしたい問題
まず全部上にしておく
それ以降の最大値と最小値に影響する
下にすると、最大値を-2,最小値も-2できる

それ以前の最大値-それ以降の最小値 は2ふえる
それ以降の最大値-それ以前の最小値 は2へる
y=xを足してみる

====答えを見た=====

maspy氏の方針がわかりやすい
https://maspypy.com/atcoder-%E5%8F%82%E5%8A%A0%E6%84%9F%E6%83%B3-2020-06-07agc045
行ける点は連番になる(偶奇は違うので注意)
x以下が可能か → 0以上x以下の点からスタートして,維持できるか

なぜ偶奇の場合分けが必要？
→平行移動が不可能だからありえない答えを生み出す可能性があるため

ある数字以外不可能な時=幅が2になり、3つの数字の可能性が生まれるが
平行移動はできないため、存在しえない数字が生まれてしまう

偶奇をちゃんとすれば問題ない


"""

from sys import stdin

S = stdin.readline()
S = S[:-1]
N = len(S)

r = 2*10**6
l = 0
while r-l != 1:
    m = (r+l)//2
    flag = False

    #even
    nmax = m//2*2
    nmin = 0
    for i in range(N):
        if S[i] == "0":
            nmax = min(nmax+1,m)
            nmin = min(nmin+1,m)
        elif S[i] == "1":
            nmax = max(nmax-1,0)
            nmin = max(nmin-1,0)
        else:
            nmax = min(nmax+1,m)
            nmin = max(nmin-1,0)
            
        if i % 2 == 0:
            if nmax % 2 == 0:
                nmax -= 1
            if nmin % 2 == 0:
                nmin += 1
        else:
            if nmax % 2 == 1:
                nmax -= 1
            if nmin % 2 == 1:
                nmin += 1

        if nmax < nmin:
            break

    if nmax >= nmin:
        flag = True
    else:
        #odd
        nmax = (m-1)//2*2+1
        nmin = 1
        for i in range(N):
            if S[i] == "0":
                nmax = min(nmax+1,m)
                nmin = min(nmin+1,m)
            elif S[i] == "1":
                nmax = max(nmax-1,0)
                nmin = max(nmin-1,0)
            else:
                nmax = min(nmax+1,m)
                nmin = max(nmin-1,0)
                
            if i % 2 == 1:
                if nmax % 2 == 0:
                    nmax -= 1
                if nmin % 2 == 0:
                    nmin += 1
            else:
                if nmax % 2 == 1:
                    nmax -= 1
                if nmin % 2 == 1:
                    nmin += 1

            if nmax < nmin:
                break
        if nmax >= nmin:
            flag = True

    if flag:
        r = m
    else:
        l = m

print (r)
