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<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<cmath>
#include<ctime>
#include<queue>
#include<map>
#include<set>
#define LL __int128
#define db double

using namespace std;
const int N=2e5+10;
int rd()
{
    int x=0,w=1;char ch=0;
    while(ch<'0'||ch>'9'){if(ch=='-') w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+(ch^48);ch=getchar();}
    return x*w;
}
int m0[N<<2],m1[N<<2];
#define mid ((l+r)>>1)
void psup(int o){m0[o]=max(m0[o<<1],m0[o<<1|1]),m1[o]=max(m1[o<<1],m1[o<<1|1]);}
void modif(int o,int l,int r,int x,int y,bool oo)
{
	if(l==r){!oo?m0[o]=y:m1[o]=y;return;}
	if(x<=mid) modif(o<<1,l,mid,x,y,oo);
	else modif(o<<1|1,mid+1,r,x,y,oo);
	psup(o);
}
int quer(int o,int l,int r,int ll,int rr,bool oo)
{
	if(ll<=l&&r<=rr) return !oo?m0[o]:m1[o];
	int an=-(1<<20);
	if(ll<=mid) an=max(an,quer(o<<1,l,mid,ll,rr,oo));
	if(rr>mid) an=max(an,quer(o<<1|1,mid+1,r,ll,rr,oo));
	return an;
}
int n,a[N],f[N][2],sm;
bool b[N],an[N];

int main()
{
	memset(m1,-0x3f3f3f,sizeof(m1));
	n=rd();
	for(int i=1,ma=0;i<=n;++i)
	{
		a[i]=rd();
		if(ma<a[i]) ma=a[i],b[i]=1,++sm;
	}
	for(int i=n;i;--i)
	{
		f[i][1]=-(1<<20);
		int xx=b[i]+1+max(0,quer(1,1,n,a[i],n,0)),yy=b[i]+1+max(0,quer(1,1,n,a[i],n,1));
		f[i][xx&1]=max(f[i][xx&1],xx);
		f[i][yy&1]=max(f[i][yy&1],yy);
		modif(1,1,n,a[i],f[i][0],0);
		modif(1,1,n,a[i],f[i][1],1);
	}
	int c0=0,c1=0,mi0=0,mi1=0;
	for(int i=1,j=sm;i<=n;++i)
	{
		j-=b[i];
		modif(1,1,n,a[i],0,0);
		modif(1,1,n,a[i],-(1<<20),1);
		int x=c0+(a[i]>=mi0)-c1+j;
		bool o=0;
		if(quer(1,1,n,max(mi1,1),n,x&1)<x)
		{
			x=c1-(c0+(a[i]>=mi0))+j;
			o=x<0||quer(1,1,n,max(mi0,a[i]),n,x&1)<x;
		}
		if(o) an[i]=1,c1+=a[i]>=mi1,mi1=max(mi1,a[i]);
		else c0+=a[i]>=mi0,mi0=max(mi0,a[i]);
	}
	c0=c1=0;
	for(int i=1,mm0=0,mm1=0;i<=n;++i)
	{
		if(!an[i])
		{
			if(mm0<a[i]) mm0=a[i],++c0;
		}
		else
		{
			if(mm1<a[i]) mm1=a[i],++c1;
		}
	}
	if(c0!=c1) puts("-1");
	else for(int i=1;i<=n;++i) printf("%d",an[i]);
    return 0;
}