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<cstdio>
#include<vector>
#define N 3000001
#include<cstring>
using namespace std;
vector<int>pans0[N],pans1[N];
int a[N],ans[N],ls1[N],ls2[N],rs1[N],rs2[N],hz[N],wei[N];
int f0l[N],f1l[N],f0r[N],f1r[N];
bool bz[N],used[N];
int X,Y,numX,numY,maxs,anss,newX,newY,n;
int max(int x,int y)
{
	if (x<y) return y;
	return x;
}
int min(int x,int y)
{
	if (x<y) return x;
	return y;
}
int find_ans1(int ma,int l,int r,int s)
{
	if (pans1[ma].size()>=1) 
		while (pans1[ma][0]>0&&used[pans1[ma][pans1[ma][0]]]==false) pans1[ma][0]--;
	if (l==r) return pans1[ma][pans1[ma][0]];
	int mid=(l+r)/2;
	int t1=0;
	if (s<=mid) t1=find_ans1(ma*2,l,mid,s);
	else	t1=find_ans1(ma*2+1,mid+1,r,s);
	return max(t1,pans1[ma][pans1[ma][0]]);
}
int find_ans0(int ma,int l,int r,int s)
{
	if (pans0[ma].size()>=1) 
		while (pans0[ma][0]>0&&used[pans0[ma][pans0[ma][0]]]==false) pans0[ma][0]--;
	if (l==r) return pans0[ma][pans0[ma][0]];
	int mid=(l+r)/2;
	int t1=0;
	if (s<=mid) t1=find_ans0(ma*2,l,mid,s);
	else	t1=find_ans0(ma*2+1,mid+1,r,s);
	return max(t1,pans0[ma][pans0[ma][0]]);
}
bool pd(int k,int p)
{
	int newX=X,newY=Y,p1=numX,p2=numY;
	if (p==0) 
	{
		if (a[k]>X) p1++;
		newX=max(a[k],X);
	} 
	else
	{
		if (a[k]>Y) p2++;
		newY=max(a[k],Y);
	}
//	if (k>=n) return true;
	if (k==n)
	{
		if (p1!=p2) return false;
		return true;
	}
	int daijia=p1-p2+hz[k+1],sp1;
	if (daijia>=0)
	{
		if (daijia%2==0)
		{
			 sp1=find_ans0(1,1,2*n,daijia);
			if (sp1>newY) return true;
		}		
		else
		{
			 sp1=find_ans1(1,1,2*n,daijia);
			if (sp1>newY) return true;
		}
	}
	daijia=p2-p1+hz[k+1];
	if (daijia>=0)
	{
		if (daijia==0) return true;
		if (daijia%2==0)
		{
			 sp1=find_ans0(1,1,2*n,daijia);
			if (sp1>newX) return true;
		}		
		else
		{
			 sp1=find_ans1(1,1,2*n,daijia);
			if (sp1>newX) return true;
		}
	}
	return false;
}
void update(int ma,int l,int r,int s,int l1,int r1,int l2,int r2)
{
	if (l==r)
	{
		f0l[ma]=l2;f0r[ma]=r2;
		f1l[ma]=l1;f1r[ma]=r1;
		return;
	}
	int mid=(l+r)/2;
	if (s<=mid) update(ma*2,l,mid,s,l1,r1,l2,r2);
	else update(ma*2+1,mid+1,r,s,l1,r1,l2,r2);
	f0l[ma]=min(f0l[ma*2],f0l[ma*2+1]);
	f1l[ma]=min(f1l[ma*2],f1l[ma*2+1]);
	f0r[ma]=max(f0r[ma*2],f0r[ma*2+1]);
	f1r[ma]=max(f1r[ma*2],f1r[ma*2+1]);
}
int find_ans(int type,int ma,int l,int r,int l1,int r1)
{
	if (l==l1&&r==r1)
	{
		if (type==1) return f1l[ma];
		if (type==2) return f1r[ma];
		if (type==3) return f0l[ma];
		if (type==4) return f0r[ma];
	}
	int mid=(l+r)/2;
	if (r1<=mid) return find_ans(type,ma*2,l,mid,l1,r1);
	if (mid<l1) return find_ans(type,ma*2+1,mid+1,r,l1,r1);
	int s1=find_ans(type,ma*2,l,mid,l1,mid);
	int s2=find_ans(type,ma*2+1,mid+1,r,mid+1,r1);
	if (type==1||type==3) return min(s1,s2);
	return max(s1,s2);
}
void update1(int ma,int l,int r,int s,int l1,int r1)
{
	if (l==l1&&r==r1)
	{
		if (pans1[ma].size()==0) pans1[ma].resize(1);
		pans1[ma][0]++;
		pans1[ma].resize(pans1[ma][0]+1);
		pans1[ma][pans1[ma][0]]=s;
		return;
	}
	int mid=(l+r)/2;
	if (r1<=mid) update1(ma*2,l,mid,s,l1,r1);
	else if (mid<l1) update1(ma*2+1,mid+1,r,s,l1,r1);
	else
	{
		update1(ma*2,l,mid,s,l1,mid);
		update1(ma*2+1,mid+1,r,s,mid+1,r1);
	}
}
void update0(int ma,int l,int r,int s,int l1,int r1)
{
	if (l==l1&&r==r1)
	{
		if (pans0[ma].size()==0) pans0[ma].resize(1);
		pans0[ma][0]++;
		pans0[ma].resize(pans0[ma][0]+1);
		pans0[ma][pans0[ma][0]]=s;
		return;
	}
	int mid=(l+r)/2;
	if (r1<=mid) update0(ma*2,l,mid,s,l1,r1);
	else if (mid<l1) update0(ma*2+1,mid+1,r,s,l1,r1);
	else
	{
		update0(ma*2,l,mid,s,l1,mid);
		update0(ma*2+1,mid+1,r,s,mid+1,r1);
	}
}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	int maxs=0;
	memset(bz,false,sizeof(bz));
	for (int i=1;i<=n;i++)
	{
		maxs=max(maxs,a[i]);
		if (a[i]==maxs)
			bz[i]=true;
	}
	for (int i=1;i<N;i++)
		f0l[i]=f1l[i]=1e9;
	for (int i=1;i<N;i++)
		pans0[i].resize(1);
	for (int i=1;i<N;i++)
		pans1[i].resize(1);
	update(1,1,n+1,n+1,1e9,0,0,0);
	for (int i=n;i>=1;i--)
	{
		if (i==3)
		{
			n++;n--;
		}
		if (bz[i])
		{
			ls1[i]=find_ans(1,1,1,n+1,a[i],n+1)+2;
			if (ls1[i]<0) ls1[i]=1;
			rs1[i]=find_ans(2,1,1,n+1,a[i],n+1)+2;
			if (rs1[i]<0) rs1[i]=1;
		}
		else
		{
			ls1[i]=find_ans(3,1,1,n+1,a[i],n+1)+1;
			rs1[i]=find_ans(4,1,1,n+1,a[i],n+1)+1;
			ls1[i]=1;
			if (rs1[i]<0) rs1[i]=1;
		}
		if (bz[i])
		{
			ls2[i]=find_ans(3,1,1,n+1,a[i],n+1)+2;
			rs2[i]=find_ans(4,1,1,n+1,a[i],n+1)+2;
			if (ls2[i]<=0) ls2[i]=2;
			if (rs2[i]<=0) rs2[i]=2;
			ls2[i]=2; 
		}
		else
		{
			ls2[i]=find_ans(1,1,1,n+1,a[i],n+1)+1;
			rs2[i]=find_ans(2,1,1,n+1,a[i],n+1)+1;
			if (ls2[i]<=0) ls2[i]=2;
			if (rs2[i]<=0) rs2[i]=2;
		}
		if (ls1[i]>rs1[i]) ls1[i]=1e9,rs1[i]=0;
		if (ls2[i]>rs2[i]) ls2[i]=1e9,rs2[i]=0;
		update(1,1,n+1,a[i],ls1[i],rs1[i],ls2[i],rs2[i]);
	}
	hz[n+1]=0;
	for (int i=n;i>=1;i--)
		if (bz[i]) hz[i]=hz[i+1]+1;
		else	hz[i]=hz[i+1];
//	for (int i=1;i<=n;i++) update(1,1,n,i,a[i]);
	X=0,Y=0,numX=0,numY=0;
	for (int i=1;i<=n;i++) wei[a[i]]=i;
	for (int i=1;i<=n;i++)
		if (ls1[wei[i]]!=1e9)
		update1(1,1,2*n,i,ls1[wei[i]],rs1[wei[i]]);
	for (int i=1;i<=n;i++)
		if (ls2[wei[i]]!=1e9)
		update0(1,1,2*n,i,ls2[wei[i]],rs2[wei[i]]);
	memset(used,true,sizeof(used));
	for (int i=1;i<=n;i++)
	{
		if (i==9)
		{
			n++;n--;
		}
		used[a[i]]=false;
		if (pd(i,0)) ans[i]=0;
		else if (pd(i,1)) ans[i]=1;
		else
		{
			printf("-1\n");
			return 0;
		}
		if (ans[i]==0)
		{
			if (X<a[i]) numX++;
			X=max(X,a[i]);
		}
		else	
		{
			if (Y<a[i]) numY++;
			Y=max(Y,a[i]);
		}
	}
	for (int i=1;i<=n;i++) printf("%d",ans[i]);
}