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<stdio.h>
#include<algorithm>
using namespace std;
int n;
int p[262144];
bool mx[262144];
int c1[262144],c2[262144];
int wz1[4194304],wz2[4194304],pre1[4194304],pre2[4194304],tim1[4194304],tim2[4194304],num1=0,num2=0;
void add(int wz,int val1,int val2,int tim)
{
	for(int i=wz;i>0;i-=(i&(-i)))
	{
		if(val1>c1[i])
		{
			wz1[num1]=i;
			pre1[num1]=c1[i];
			tim1[num1]=tim;
			num1++;
			c1[i]=val1;
		}
		if(val2>c2[i])
		{
			wz2[num2]=i;
			pre2[num2]=c2[i];
			tim2[num2]=tim;
			num2++;
			c2[i]=val2;
		}
	}
}
void query(int wz,int& val1,int& val2)
{
	val1=-999999;
	val2=0;
	for(int i=wz;i<=n;i+=(i&(-i)))
	{
		if(c1[i]>val1)
		{
			val1=c1[i];
		}
		if(c2[i]>val2)
		{
			val2=c2[i];
		}
	}
}
void del(int tim)
{
	while(num1)
	{
		if(tim1[num1-1]!=tim)
		{
			break;
		}
		num1--;
		c1[wz1[num1]]=pre1[num1];
	}
	while(num2)
	{
		if(tim2[num2-1]!=tim)
		{
			break;
		}
		num2--;
		c2[wz2[num2]]=pre2[num2];
	}
}
bool chk2(int val,int val1,int val2)
{
	if(val<0)
	{
		return false;
	}
	if(val&1)
	{
		return val<=val1;
	}
	return val<=val2;
}
bool chk(int numx,int numy,int mxx,int mxy,int m)
{
	int val1,val2;
	query(mxx,val1,val2);
	if(chk2(numy-numx+m,val1,val2))
	{
		return true;
	}
	query(mxy,val1,val2);
	return chk2(numx-numy+m,val1,val2);
}
int main()
{
	int last=0;
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&p[i]);
		if(p[i]>last)
		{
			mx[i]=true;
			last=p[i];
		}
		c1[i]=-999999;
		c2[i]=0;
	}
	int m=0;
	for(int i=n;i>=1;i--)
	{
		int val1,val2;
		query(p[i],val1,val2);
		if(mx[i])
		{
			m++;
			add(p[i],val1+2,val2+2,i);
		}
		else
		{
			add(p[i],val2+1,val1+1,i);
		}
	}
	int numx=0,numy=0,mxx=1,mxy=1;
	if(!chk(numx,numy,mxx,mxy,m))
	{
		printf("-1\n");
		return 0;
	}
	for(int i=1;i<=n;i++)
	{
		del(i);
		if(mx[i])
		{
			m--;
		}
		int numx2=numx,numy2=numy,mxx2=mxx,mxy2=mxy;
		if(p[i]>=mxx)
		{
			mxx2=p[i];
			numx2++;
		}
		if(p[i]>=mxy)
		{
			mxy2=p[i];
			numy2++;
		}
		if(chk(numx2,numy,mxx2,mxy,m))
		{
			putchar('0');
			numx=numx2;
			mxx=mxx2;
		}
		else
		{
			putchar('1');
			numy=numy2;
			mxy=mxy2;
		}
	}
	putchar('\n');
	return 0;
}