Given is a string S, where each character is `0`, `1`, or `?`.

Consider making a string S' by replacing each occurrence of `?` with `0` or `1` (we can choose the character for each `?` independently). Let us define the unbalancedness of S' as follows:

* (The unbalancedness of S') = \max \\{ The absolute difference between the number of occurrences of `0` and `1` between the l-th and r-th character of S (inclusive) :\ 1 \leq l \leq r \leq |S|\\}



Find the minimum possible unbalancedness of S'.

Constraints

* 1 \leq |S| \leq 10^6
* Each character of S is `0`, `1`, or `?`.

Input

Input is given from Standard Input in the following format:


S


Output

Print the minimum possible unbalancedness of S'.

Examples

Input

0??


Output

1


Input

0??0


Output

2


Input

??00????0??0????0?0??00??1???11?1?1???1?11?111???1


Output

4
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
const int N=1e6+7,INF=0x3f3f3f3f,sgn[]={-1,1};
char a[N];
int n,s[N],nxt[N];
int solve(int x,int cnt=0){
	int w=0;
	FOR(i,1,n){
		if(a[i]=='?'&&cnt+2+nxt[i]<=x)cnt+=2;
		w=min(w,s[i]+cnt);
	}
	return x-w;
}
int main(){
	scanf("%s",a+1),n=strlen(a+1),nxt[n+1]=-INF;
	FOR(i,1,n)s[i]=s[i-1]+sgn[a[i]=='1'];
	ROF(i,n,0)nxt[i]=max(nxt[i+1],s[i]);
	cout<<min(solve(nxt[0]),solve(nxt[0]+1));
	return 0;
}