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 LL long long

using namespace std;
const int N=2e5+10,inf=1<<30;
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 mx[2][N<<2];
void psup(int o){mx[0][o]=max(mx[0][o<<1],mx[0][o<<1|1]),mx[1][o]=max(mx[1][o<<1],mx[1][o<<1|1]);}
void modif(int o,int l,int r,int lx,int x,int ty)
{
    if(l==r){mx[ty][o]=x;return;}
    int mid=(l+r)>>1;
    if(lx<=mid) modif(o<<1,l,mid,lx,x,ty);
    else modif(o<<1|1,mid+1,r,lx,x,ty);
    psup(o);
}
int quer(int o,int l,int r,int ll,int rr,int ty)
{
    if(ll<=l&&r<=rr) return mx[ty][o];
    int an=-inf,mid=(l+r)>>1;
    if(ll<=mid) an=max(an,quer(o<<1,l,mid,ll,rr,ty));
    if(rr>mid) an=max(an,quer(o<<1|1,mid+1,r,ll,rr,ty));
    return an;
}
int n,m,a[N],ps[N],va[N],an[N],sm;
void bui(int o,int l,int r)
{
    mx[0][o]=mx[1][o]=-inf;
    if(l==r) return;
    int mid=(l+r)>>1;
    bui(o<<1,l,mid),bui(o<<1|1,mid+1,r);
}

int main()
{
    n=rd(),m=n+1;
    for(int i=1,mx=0;i<=n;++i)
    {
	a[i]=rd(),ps[a[i]]=i;
	mx=max(mx,a[i]);
	va[i]=1+(mx==a[i]),sm+=mx==a[i];
    }
    bui(1,1,m);
    modif(1,1,m,n+1,0,0);
    for(int i=n;i;--i)
    {
	int dt0=quer(1,1,m,a[i]+1,m,va[i]&1)+va[i],dt1=quer(1,1,m,a[i]+1,m,(va[i]^1)&1)+va[i];
	modif(1,1,m,a[i],dt0,0),modif(1,1,m,a[i],dt1,1);
    }
    for(int i=1,m0=0,m1=0,c0=0,c1=0;i<=n;++i)
    {
	modif(1,1,m,a[i],-inf,0),modif(1,1,m,a[i],-inf,1);
	sm-=va[i]-1;
	int nm0=max(m0,a[i]),nm1=m1,nc0=c0+(nm0==a[i]),nc1=c1,xx;
	xx=sm+nc1-nc0;
	if(xx>=0&&quer(1,1,m,nm0+1,m,xx&1)>=xx)
	{
	    an[i]=0,m0=nm0,m1=nm1,c0=nc0,c1=nc1;
	    continue;
	}
	xx=sm+nc0-nc1;
	if(xx>=0&&quer(1,1,m,nm1+1,m,xx&1)>=xx)
	{
	    an[i]=0,m0=nm0,m1=nm1,c0=nc0,c1=nc1;
	    continue;
	}
	nm0=m0,nm1=max(m1,a[i]),nc0=c0,nc1=c1+(nm1==a[i]);
	xx=sm+nc1-nc0;
	if(xx>=0&&quer(1,1,m,nm0+1,m,xx&1)>=xx)
	{
	    an[i]=1,m0=nm0,m1=nm1,c0=nc0,c1=nc1;
	    continue;
	}
	xx=sm+nc0-nc1;
	if(xx>=0&&quer(1,1,m,nm1+1,m,xx&1)>=xx)
	{
	    an[i]=1,m0=nm0,m1=nm1,c0=nc0,c1=nc1;
	    continue;
	}
	puts("-1");
	return 0;
    }
    for(int i=1;i<=n;++i) printf("%d",an[i]);
    return 0;
}