Problem: You are given P, a permutation of (1,\ 2,\ ...\ N).

A string S of length N consisting of `0` and `1` is a good string when it meets the following criterion:

* The sequences X and Y are constructed as follows:
* First, let X and Y be empty sequences.
* For each i=1,\ 2,\ ...\ N, in this order, append P_i to the end of X if S_i= `0`, and append it to the end of Y if S_i= `1`.
* If X and Y have the same number of high elements, S is a good string. Here, the i-th element of a sequence is called high when that element is the largest among the elements from the 1-st to i-th element in the sequence.



Determine if there exists a good string. If it exists, find the lexicographically smallest such string.

Constraints

* 1 \leq N \leq 2 \times 10^5
* 1 \leq P_i \leq N
* P_1,\ P_2,\ ...\ P_N are all distinct.
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N
P_1 P_2 ... P_N


Output

If a good string does not exist, print `-1`. If it exists, print the lexicographically smallest such string.

Examples

Input

6
3 1 4 6 2 5


Output

001001


Input

5
1 2 3 4 5


Output

-1


Input

7
1 3 2 5 6 4 7


Output

0001101


Input

30
1 2 6 3 5 7 9 8 11 12 10 13 16 23 15 18 14 24 22 26 19 21 28 17 4 27 29 25 20 30


Output

000000000001100101010010011101

Solution (in CPP):

Solution:
#include<iostream>
#include<queue>
using namespace std;
const int N=2e5+2;
const int inf=1e9+7;
int ar[N],dp[N][2],odd[4*N],even[4*N],cnt[N];
bool rec[N];
queue<int> lis;
void init(int idx,int l,int r){
	if(l==r){
		odd[idx]=-1;
		return;
	}
	init(2*idx,l,(l+r)/2);
	init(2*idx+1,(l+r)/2+1,r);
	odd[idx]=-1;
}
int getmaxodd(int idx,int l,int r,int lef,int rig){
	if(l>rig||r<lef){
		return -inf;
	}
	if(l>=lef&&r<=rig){
		return odd[idx];
	}
	return max(getmaxodd(2*idx,l,(l+r)/2,lef,rig),getmaxodd(2*idx+1,(l+r)/2+1,r,lef,rig));
}
int getmaxeven(int idx,int l,int r,int lef,int rig){
	if(l>rig||r<lef){
		return -inf;
	}
	if(l>=lef&&r<=rig){
		return even[idx];
	}
	return max(getmaxeven(2*idx,l,(l+r)/2,lef,rig),getmaxeven(2*idx+1,(l+r)/2+1,r,lef,rig));	
}
void updodd(int idx,int l,int r,int pos,int val){
	if(l>pos||r<pos){
		return;
	}
	if(l==r){
		odd[idx]=val;
		return;
	}
	updodd(2*idx,l,(l+r)/2,pos,val);
	updodd(2*idx+1,(l+r)/2+1,r,pos,val);
	odd[idx]=max(odd[2*idx],odd[2*idx+1]);
}
void updeven(int idx,int l,int r,int pos,int val){
	if(l>pos||r<pos){
		return;
	}
	if(l==r){
		even[idx]=val;
		return;
	}
	updeven(2*idx,l,(l+r)/2,pos,val);
	updeven(2*idx+1,(l+r)/2+1,r,pos,val);
	even[idx]=max(even[2*idx],even[2*idx+1]);
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,i,j=0,k,l,num1=0,num2=0,max1=0,max2=0,wow;
	cin>>n;
	for(i=1;i<=n;i++){
		cin>>ar[i];
		cnt[i]=cnt[i-1];
		if(ar[i]>j){
			j=ar[i];
			rec[i]=true;
			cnt[i]++;
		}
	}
	init(1,1,n);
	for(i=n;i>=1;i--){
		if(rec[i]){
			dp[i][0]=getmaxeven(1,1,n,ar[i],n)+2;
			dp[i][1]=getmaxodd(1,1,n,ar[i],n)+2;
			if(dp[i][1]==1){
				dp[i][1]=-1;
			}
			updodd(1,1,n,ar[i],dp[i][1]);
			updeven(1,1,n,ar[i],dp[i][0]);
		}
		else{
			dp[i][0]=getmaxodd(1,1,n,ar[i],n)+1;
			dp[i][1]=getmaxeven(1,1,n,ar[i],n)+1;
			updeven(1,1,n,ar[i],dp[i][0]);
			updodd(1,1,n,ar[i],dp[i][1]);
		}
		//cout<<i<<' '<<dp[i][0]<<' '<<dp[i][1]<<' '<<endl;
	}
	//true
	for(i=1;i<=n;i++){
		updodd(1,1,n,ar[i],dp[i][1]);
		updeven(1,1,n,ar[i],dp[i][0]);
	}
	for(i=1;i<=n;i++){
		wow=cnt[n]-cnt[i];
		j=num1;
		k=num2;
		updodd(1,1,n,ar[i],-1);
		updeven(1,1,n,ar[i],0);
		if(ar[i]>max1){
			j++;
			if(((j-k+wow)&1)){
				if(j-k+wow>=0&&getmaxodd(1,1,n,max2+1,n)>=j-k+wow){
					lis.push(0);
//					if(i==3){
//						cout<<getmaxodd(1,1,n,max2+1,n)<<' '<<j-k+wow<<endl;
//					}
					max1=ar[i];
					num1++;
					continue;
				}
				if(k-j+wow>=0&&getmaxodd(1,1,n,ar[i]+1,n)>=k-j+wow){
					lis.push(0);
//					if(i==3){
//						cout<<getmaxodd(1,1,n,ar[i]+1,n)<<' '<<k-j+wow<<" cac"<<endl;
//					}
					max1=ar[i];
					num1++;
					continue;
				}
			}
			else{
				if(j-k+wow>=0&&getmaxeven(1,1,n,max2+1,n)>=j-k+wow){
					lis.push(0);
					max1=ar[i];
					num1++;
					continue;
				}
				if(k-j+wow>=0&&getmaxeven(1,1,n,ar[i]+1,n)>=k-j+wow){
					lis.push(0);
					max1=ar[i];
					num1++;
					continue;
				}
			}
		}
		else{
			if(((j-k+wow)&1)){
				if(j-k+wow>=0&&getmaxodd(1,1,n,max2+1,n)>=j-k+wow){
					lis.push(0);
					continue;
				}
				if(k-j+wow>=0&&getmaxodd(1,1,n,max1+1,n)>=k-j+wow){
					lis.push(0);
					continue;
				}
			}
			else{
				if(j-k+wow>=0&&getmaxeven(1,1,n,max2+1,n)>=j-k+wow){
					lis.push(0);
					continue;
				}
				if(k-j+wow>=0&&getmaxeven(1,1,n,max1+1,n)>=k-j+wow){
					lis.push(0);
					continue;
				}
			}
		}
		j=num1;
		k=num2;
		if(ar[i]>max2){
			k++;
			if(((j-k+wow)&1)){
				if(j-k+wow>=0&&getmaxodd(1,1,n,ar[i]+1,n)>=j-k+wow){
					lis.push(1);
					max2=ar[i];
					num2++;
					continue;
				}
				if(k-j+wow>=0&&getmaxodd(1,1,n,max1+1,n)>=k-j+wow){
					lis.push(1);
					max2=ar[i];
					num2++;
					continue;
				}
			}
			else{
				if(j-k+wow>=0&&getmaxeven(1,1,n,ar[i]+1,n)>=j-k+wow){
					lis.push(1);
					max2=ar[i];
					num2++;
					continue;
				}
				if(k-j+wow>=0&&getmaxeven(1,1,n,max1+1,n)>=k-j+wow){
					lis.push(1);
					max2=ar[i];
					num2++;
					continue;
				}
			}
		}
		else{
			if(((j-k+wow)&1)){
				if(j-k+wow>=0&&getmaxodd(1,1,n,max2+1,n)>=j-k+wow){
					lis.push(1);
					continue;
				}
				if(k-j+wow>=0&&getmaxodd(1,1,n,max1+1,n)>=k-j+wow){
					lis.push(1);
					continue;
				}
			}
			else{
				if(j-k+wow>=0&&getmaxeven(1,1,n,max2+1,n)>=j-k+wow){
					lis.push(1);
					continue;
				}
				if(k-j+wow>=0&&getmaxeven(1,1,n,max1+1,n)>=k-j+wow){
					lis.push(1);
					continue;
				}
			}
		}
		cout<<"-1";
		return 0;
	}
	while(lis.size()){
		cout<<lis.front();
		lis.pop();
	}
}