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 _ 200005
#define ll long long
using namespace std;

#define inf 1000000007
IL int gi(){
	int data=0,fu=1; char ch=0; while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
	if(ch=='-')fu=-1,ch=getchar();
	while('0'<=ch&&ch<='9')data=(data<<1)+(data<<3)+(ch^48),ch=getchar(); return data*fu;
}

int bit[_][2],f[_][2],mx[40*_][2],lson[40*_],rson[40*_],rt[_],Q[_],n,m,oo;
int P[_]; bool Is[_];
IL void Insert(int op,int ps,int fv){
	while(ps)bit[ps][op]=max(bit[ps][op],fv),ps-=ps&-ps; return; 
}
IL int Query(int op,int ps){
	int ret=-inf; while(ps<=n)ret=max(ret,bit[ps][op]),ps+=ps&-ps; return ret;
}
void Insert(int &o,int l,int r,int ps,int id){
	lson[++oo]=lson[o]; rson[oo]=rson[o]; mx[oo][0]=mx[o][0]; mx[oo][1]=mx[o][1];
	o=oo;
	mx[o][0]=max(mx[o][0],f[id][0]),mx[o][1]=max(mx[o][1],f[id][1]); 
	if(l==r)return; int mid=(l+r)>>1;
	ps<=mid?Insert(lson[o],l,mid,ps,id):Insert(rson[o],mid+1,r,ps,id); return; 
}
int Query(int o,int l,int r,int ql,int qr,int op){
	if(ql<=l&&r<=qr)return mx[o][op]; int mid=(l+r)>>1,v=-inf;
	if(ql<=mid)v=max(v,Query(lson[o],l,mid,ql,qr,op));
	if(qr >mid)v=max(v,Query(rson[o],mid+1,r,ql,qr,op));
	return v; 
}
IL bool Check(int la,int lb,int mv,int i){
	if(i>n)return true; int vl=la+Q[i]-lb,t=(vl&1); if(vl<0)return false; 
	//cout<<i<<": "<<"la="<<la<<"; lb="<<lb<<" ; mv="<<mv<<" ; Qry="<<Query(rt[i],1,n,mv,n,t)<<" ; vl="<<vl<<endl; 
	return Query(rt[i],1,n,mv,n,t)>=vl; 
}
int main(){
	n=gi(); for(int i=1;i<=n;++i)P[i]=gi();
	for(int i=1,mv=0;i<=n;++i)mv=max(mv,P[i]),Is[i]=(mv==P[i]);
	for(int i=n;i>=1;--i)Q[i]=Q[i+1]+Is[i];
	for(int i=n;i>=1;--i)bit[i][0]=bit[i][1]=-inf; Insert(0,n,0); 
	for(int i=n;i>=1;--i){
		if(!Is[i])f[i][0]=Query(1,P[i])+1,f[i][1]=Query(0,P[i])+1;
		else f[i][0]=Query(0,P[i])+2,f[i][1]=Query(1,P[i])+2;
		Insert(0,P[i],f[i][0]);
		Insert(1,P[i],f[i][1]);
		rt[i]=rt[i+1],Insert(rt[i],1,n,P[i],i); 
	}
	string sx,sy;
	sx.clear(); sy.clear();
	//fix X; Y nolimit
	for(int i=1,la=0,lb=0,ma=0,mb=0;i<=n;++i){
		if(i==n){
			if(la+(P[i]>ma)==lb)sx+='0';
			else if(la==lb+(P[i]>mb))sx+='1'; else sx[0]='2';
			break; 
		}
		if(!(!Is[i]&&P[i]>ma)&&Check(la+(P[i]>ma),lb,mb,i+1))sx+='0',la+=(P[i]>ma),ma=max(ma,P[i]);
		else sx+='1',lb+=(P[i]>mb),mb=max(mb,P[i]);
		if(!Check(la,lb,mb,i+1)){sx[0]='2'; break;}
	}
	//fix Y; X nolimit
	for(int i=1,la=0,lb=0,ma=0,mb=0;i<=n;++i){
		if(i==n){
			if(la+(P[i]>ma)==lb)sy+='0';
			else if(la==lb+(P[i]>mb))sy+='1'; else sy[0]='2';
			break; 
		}
		if(Check(lb,la+(P[i]>ma),max(ma,P[i]),i+1))sy+='0',la+=(P[i]>ma),ma=max(ma,P[i]);
		else if((!Is[i]&&P[i]>mb)||!Check(lb+(P[i]>mb),la,ma,i+1)){sy[0]='2'; break; }
		else sy+='1',lb+=(P[i]>mb),mb=max(mb,P[i]);
		//cout<<i<<": "<<sy<<" "<<endl;
	}
	//cout<<sx<<" "<<sy<<endl;
	if(sx[0]=='2'&&sy[0]=='2')return puts("-1"),0;
	if(sx>sy)swap(sx,sy);
	cout<<sx<<endl;
	return 0;	
}