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>
using namespace std;
#define REP(i,a,b) for(int i=(a),ed=(b);i<=ed;++i)
#define DREP(i,a,b) for(int i=(a),ed=(b);i>=ed;--i)
typedef long long ll;
inline int read(){
    register int x=0,f=1;register char ch=getchar();
    while(!isdigit(ch)){if(ch=='-')f=0;ch=getchar();}
    while(isdigit(ch)){x=x*10+(ch^'0');ch=getchar();}
    return f?x:-x; 
}

const int N=2e5+10;
int n,a[N],s[N],len[2],stk[2][N],mx[2][N],sum[2],maxn[N],sufsum[N];

int tr[N*50],ch[N*50][2],cnt;
struct SegmentTree{
    int rt[N];
    inline void pushup(int x){tr[x]=max(tr[ch[x][0]],tr[ch[x][1]]);}
    inline void Insert(int &p,int pre,int l,int r,int pos,int v){
	p=++cnt;if(l==r){tr[p]=max(tr[p],v);return;}
	int mid=(l+r)>>1;
	if(pos<=mid){ch[p][1]=ch[pre][1];Insert(ch[p][0],ch[pre][0],l,mid,pos,v);}
	else{ch[p][0]=ch[pre][0];Insert(ch[p][1],ch[pre][1],mid+1,r,pos,v);}
	pushup(p);
    }
    inline int Query(int p,int l,int r,int L,int R){
	if(!p||L>R)return 0;
	if(L<=l&&r<=R)return tr[p];
	int mid=(l+r)>>1,res=0;
	if(L<=mid)res=max(res,Query(ch[p][0],l,mid,L,R));
	if(mid<R)res=max(res,Query(ch[p][1],mid+1,r,L,R));
	return res;
    }
}T[2];

inline bool check(int op,int i){
    int ned=sum[op]+sufsum[i+1]-sum[op^1];
    if(ned<0)return 0;
    return T[ned&1].Query(T[ned&1].rt[i+1],1,n,mx[op^1][len[op^1]]+1,n)>=ned;
}

int main(){
//    freopen("in.in","r",stdin);freopen("out.out","w",stdout);
    n=read();REP(i,1,n)a[i]=read(),maxn[i]=max(maxn[i-1],a[i]);
    DREP(i,n,1)sufsum[i]=sufsum[i+1]+(a[i]==maxn[i]);
    DREP(i,n,1){
	int t0=T[0].Query(T[0].rt[i+1],1,n,a[i]+1,n),t1=T[1].Query(T[1].rt[i+1],1,n,a[i]+1,n);
//	cout<<t0<<' '<<t1<<endl;
	if(a[i]==maxn[i]){
	    T[0].Insert(T[0].rt[i],T[0].rt[i+1],1,n,a[i],t0+2);
	    if(t1)T[1].Insert(T[1].rt[i],T[1].rt[i+1],1,n,a[i],t1+2);
	    else T[1].rt[i]=T[1].rt[i+1];
	}
	else{
	    T[1].Insert(T[1].rt[i],T[1].rt[i+1],1,n,a[i],t0+1);
	    if(t1)T[0].Insert(T[0].rt[i],T[0].rt[i+1],1,n,a[i],t1+1);
	    else T[0].rt[i]=T[0].rt[i+1];
	}
    }
    REP(i,1,n){
	s[i]=-1;
	REP(j,0,1){
	    stk[j][++len[j]]=a[i];
	    mx[j][len[j]]=max(mx[j][len[j]-1],a[i]);
	    sum[j]+=(mx[j][len[j]]==a[i]);
	    if(check(0,i)){s[i]=j;break;}
	    if(check(1,i)){s[i]=j;break;}
	    sum[j]-=(mx[j][len[j]]==a[i]);
	    --len[j];
	}
	if(!~s[i]){puts("-1");return 0;}
    }
    REP(i,1,n)printf("%d",s[i]);
    puts("");
    return 0;
}