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>
using namespace std;
#define ll long long
#define REP(i,a,b) for(int i=(a),_end_=(b);i<=_end_;i++)
#define DREP(i,a,b) for(int i=(a),_end_=(b);i>=_end_;i--)
#define EREP(i,a) for(int i=start[(a)];i;i=e[i].next)
template<class T>inline void chkmax(T &a,T b){ if(a<b)a=b;}
template<class T>inline void chkmin(T &a,T b){ if(a>b)a=b;}
#define fi first
#define se second
#define mkr(a,b) make_pair(a,b)
#define SZ(A) ((int)A.size())
inline int read()
{
    int sum=0,p=1;char ch=getchar();
    while(!(('0'<=ch && ch<='9') || ch=='-'))ch=getchar();
    if(ch=='-')p=-1,ch=getchar();
    while('0'<=ch && ch<='9')sum=sum*10+ch-48,ch=getchar();
    return sum*p;
}

const int maxn=2e5+20;
const int inf=0x3f3f3f3f;

int n;
int p[maxn];

struct node {
    int mx[2];
    node(){ mx[0]=0; mx[1]=-inf;}
    inline void Merge(node lc,node rc){
	mx[0]=max(lc.mx[0],rc.mx[0]);
	mx[1]=max(lc.mx[1],rc.mx[1]);
    }
};
node c[(1<<19)+20];

int val[maxn];

int f[maxn][2];

#define lc (o<<1)
#define rc (o<<1|1)
#define left lc,l,mid
#define right rc,mid+1,r

void update(int x,int *d,int o,int l,int r)
{
    if(l==r)return c[o].mx[0]=d[0],c[o].mx[1]=d[1],void();
    int mid=l+r>>1;
    if(x<=mid)update(x,d,left);
    else update(x,d,right);
    c[o].Merge(c[lc],c[rc]);
}

node query(int ql,int qr,int o,int l,int r)
{
    if(ql>qr)return node();
    if(ql<=l && r<=qr)return c[o];
    int mid=l+r>>1;
    if(qr<=mid)return query(ql,qr,left);
    else if(ql>mid)return query(ql,qr,right);
    else {
	node x; x.Merge(query(ql,qr,left),query(ql,qr,right));
	chkmax(x.mx[0],0);
	return x;
    }
}

/*void make_tree(int o,int l,int r)
{
    c[o].mx[0]=f[l][0]; c[o].mx[1]=f[l][1];
    if(l==r)return;
    int mid=l+r>>1;
    make_tree(left);
    make_tree(right);
    }*/

inline void init()
{
    n=read();
    REP(i,1,n)p[i]=read();
    int mx=0;
    REP(i,1,n)
    {
	val[i]=1;
	if(p[i]>mx)mx=p[i],val[i]=2;
    }
    DREP(i,n,1)
    {
	node t=query(p[i],n,1,1,n);
	f[i][0]=t.mx[val[i]&1]+val[i];
	f[i][1]=t.mx[~val[i]&1]+val[i];
	chkmax(f[i][0],0);
	update(p[i],f[i],1,1,n);
    }
}

int ans[maxn];

inline void doing()
{
    
    int A=0,B=0,Q=0,maxA=0,maxB=0;
    REP(i,1,n)Q+=val[i]==2;

    {
	node t=query(1,n,1,1,n);
	if(t.mx[Q&1]<Q)puts("-1"),exit(0);
    }
	    
    REP(i,1,n)
    {
	int mx[2]={0,0};
	update(p[i],mx,1,1,n);
	int flg0=0,nA,nB,nQ;
	//check0
	{
	    nA=A+(p[i]>maxA),nB=B,nQ=Q-(val[i]==2);
	    {
		int ned=nA+nQ-nB;
		node t=query(maxB+1,n,1,1,n);
		if(ned>=0 && t.mx[ned&1]>=ned)flg0=1;
	    }
	    {
		int ned=nB+nQ-nA;
		node t=query(max(maxA,p[i])+1,n,1,1,n);
		if(ned>=0 && t.mx[ned&1]>=ned)flg0=1;
	    }
	}
	if(flg0)
	{
	    A+=p[i]>maxA; Q-=val[i]==2;
	    ans[i]=0;
	    chkmax(maxA,p[i]);
	}else
	{
	    B+=p[i]>maxB; Q-=val[i]==2;
	    ans[i]=1;
	    chkmax(maxB,p[i]);
	}
    }
    REP(i,1,n)printf("%d",ans[i]);
}

int main()
{

    init();
    doing();
    return 0;
}