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 fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

typedef long long LL;

const int maxn=2e5+5;

int n,a[maxn],Q;
bool takai[maxn];

int tr[2][4*maxn];
int tr_cx(int ty,int k,int l,int r,int x)
{
	if (x>n) return 0;
	int re=0;
	while (l<r)
	{
		int t=k<<1, mid=(l+r)>>1;
		if (x<=mid) re=max(re,tr[ty][t+1]), k=t, r=mid;
			else k=t+1, l=mid+1;
	}
	return max(re,tr[ty][k]);
}
void tr_xg(int ty,int k,int l,int r,int x,int z)
{
	if (l==r)
	{
		tr[ty][k]=z;
		return;
	}
	int t=k<<1, mid=(l+r)>>1;
	if (x<=mid) tr_xg(ty,t,l,mid,x,z); else tr_xg(ty,t+1,mid+1,r,x,z);
	tr[ty][k]=max(tr[ty][t],tr[ty][t+1]);
}

bool check(int hx,int hy,int cx,int cy,int ai)
{
	if (ai>hx) hx=ai, cx++;
	int ned=cx-cy+Q;
	if (ned>=0 && (tr_cx(1,1,1,n,hy+1)>=ned || !(ned&1) && tr_cx(0,1,1,n,hy+1)>=ned)) return 1;
	ned=cy-cx+Q;
	if (ned>=0 && (tr_cx(1,1,1,n,hx+1)>=ned || !(ned&1) && tr_cx(0,1,1,n,hx+1)>=ned)) return 1;
	return 0;
}

char ans[maxn];
int main()
{
	scanf("%d",&n);
	int maxa=0;
	fo(i,1,n)
	{
		scanf("%d",&a[i]);
		if (a[i]>maxa)
		{
			takai[i]=1;
			maxa=a[i];
			Q++;
		}
	}
	
	fd(i,n,1)
	{
		int tr0=tr_cx(0,1,1,n,a[i]+1), tr1=tr_cx(1,1,1,n,a[i]+1), f0, f1;
		if (takai[i]) f0=tr0+2, f1=(tr1) ?tr1+2 :0 ;
			else f0=0, f1=max(tr0,tr1)+1;
		tr_xg(0,1,1,n,a[i],f0);
		tr_xg(1,1,1,n,a[i],f1);
	}
	
	int hx=0, hy=0, cx=0, cy=0;
	fo(i,1,n)
	{
		Q-=takai[i];
		tr_xg(0,1,1,n,a[i],0);
		tr_xg(1,1,1,n,a[i],0);
		if (check(hx,hy,cx,cy,a[i]))
		{
			ans[i]='0';
			if (a[i]>hx) hx=a[i], cx++;
		} else if (check(hy,hx,cy,cx,a[i]))
		{
			ans[i]='1';
			if (a[i]>hy) hy=a[i], cy++;
		} else
		{
			puts("-1");
			return 0;
		}
	}
	
	printf("%s\n",ans+1);
}