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<bits/stdc++.h>
    #define il inline
    #define vd void
    typedef long long ll;
    il ll gi(){
    	ll x=0,f=1;
    	char ch=getchar();
    	while(!isdigit(ch))f^=ch=='-',ch=getchar();
    	while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    	return f?x:-x;
    }
    int n,p[200010];
    int f[2][200010],ismx[200010];
    struct segtree{
    #define mid ((l+r)>>1)
    	int rt[200010],ls[6000010],rs[6000010],mx[6000010],cnt;
    	il vd update(int&x,int l,int r,const int&p,const int&d){
    		++cnt;ls[cnt]=ls[x],rs[cnt]=rs[x],mx[cnt]=mx[x];x=cnt;
    		if(l==r){mx[x]=d;return;}
    		if(d>mx[x])mx[x]=d;
    		if(p<=mid)update(ls[x],l,mid,p,d);
    		else update(rs[x],mid+1,r,p,d);
    	}
    	il int query(int x,int l,int r,const int&L){
    		if(L<=l)return mx[x];
    		if(L<=mid)return std::max(query(ls[x],l,mid,L),query(rs[x],mid+1,r,L));
    		else return query(rs[x],mid+1,r,L);
    	}
    #undef mid
    }T0,T1;
    char ans1[200010],ans2[200010];
    il int Query(int c,int l,int p){
    	if(l>n)return c?-1e9:0;
    	if(!c)return T0.query(T0.rt[l],1,n,p);
    	else return T1.query(T1.rt[l],1,n,p);
    }
    int main(){
    #ifdef XZZSB
    	freopen("in.in","r",stdin);
    	freopen("out.out","w",stdout);
    #endif
    	n=gi();
    	for(int i=1;i<=n;++i)p[i]=gi();
    	int la1=0,lb1=0,la2=0,lb2=0,mxa1=0,mxa2=0,mxb1=0,mxb2=0,rest=0;
    	for(int i=1,mx=0;i<=n;++i)if(p[i]>mx)mx=p[i],ismx[i]=1,++rest;
    	memset(T1.mx,-63,sizeof T1.mx);
    	for(int i=n;i;--i){
    		T0.rt[i]=T0.rt[i+1];T1.rt[i]=T1.rt[i+1];
    		if(ismx[i])f[0][i]=T0.query(T0.rt[i],1,n,p[i])+2,f[1][i]=T1.query(T1.rt[i],1,n,p[i])+2;
    		else f[0][i]=T1.query(T1.rt[i],1,n,p[i])+1,f[1][i]=T0.query(T0.rt[i],1,n,p[i])+1;
    		T0.update(T0.rt[i],1,n,p[i],f[0][i]);T1.update(T1.rt[i],1,n,p[i],f[1][i]);
    	}
    	auto adda1=[&](int x){if(x>mxa1)++la1,mxa1=x;};
    	auto adda2=[&](int x){if(x>mxa2)++la2,mxa2=x;};
    	auto addb1=[&](int x){if(x>mxb1)++lb1,mxb1=x;};
    	auto addb2=[&](int x){if(x>mxb2)++lb2,mxb2=x;};
    	for(int i=1;i<=n;++i){
    		int c=la1+rest-lb1+(p[i]>mxa1)-ismx[i];
    		if(c>=0&&Query(c&1,i+1,mxb1)>=c)ans1[i]='0',adda1(p[i]);
    		else ans1[i]='1',addb1(p[i]);
    		c=la2+rest-lb2-(p[i]>mxb2)-ismx[i];
    		if(c>=0&&Query(c&1,i+1,std::max(p[i],mxb2))>=c)ans2[i]='0',addb2(p[i]);
    		else ans2[i]='1',adda2(p[i]);
    		if(ismx[i])--rest;
    	}
    	if(la1==lb1&&la2==lb2){
    		if(strcmp(ans1+1,ans2+1)<0)printf("%s",ans1+1);
    		else printf("%s",ans2+1);
    	}else if(la1==lb1)printf("%s",ans1+1);
    	else if(la2==lb2)printf("%s",ans2+1);
    	else puts("-1");
    	return 0;
    }