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 <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#define ll long long
#define inf 0x3f3f3f3f
#define maxn 200010
inline ll read()
{
    ll x=0; char c=getchar(),f=1;
    for(;c<'0'||'9'<c;c=getchar())if(c=='-')f=-1;
    for(;'0'<=c&&c<='9';c=getchar())x=x*10+c-'0';
    return x*f;
}
inline void write(ll x)
{
    static int buf[20],len; len=0;
    if(x<0)x=-x,putchar('-');
    for(;x;x/=10)buf[len++]=x%10;
    if(!len)putchar('0');
    else while(len)putchar(buf[--len]+'0');
}
inline void writeln(ll x){write(x); putchar('\n');}
inline void writesp(ll x){write(x); putchar(' ');}
struct Segment_Tree{
	int sgt[4*maxn];
	void build(int now,int l,int r,int k)
	{
		sgt[now]=k;
		if(l<r){
			int mid=(l+r)>>1;
			build(now<<1,l,mid,k); build(now<<1|1,mid+1,r,k);
		}
	}
	void modify(int now,int l,int r,int x,int k)
	{
		if(l==r)sgt[now]=k;
		else{
			int mid=(l+r)>>1;
			if(x<=mid)modify(now<<1,l,mid,x,k);
			else modify(now<<1|1,mid+1,r,x,k);
			sgt[now]=std::max(sgt[now<<1],sgt[now<<1|1]);
		}
	}
	int query(int now,int l,int r,int x,int y)
	{
		if(x<=l&&r<=y)return sgt[now];
		else{
			int mid=(l+r)>>1,cur=-inf;
			if(x<=mid)cur=std::max(cur,query(now<<1,l,mid,x,y));
			if(mid<y)cur=std::max(cur,query(now<<1|1,mid+1,r,x,y));
			return cur;
		}
	}
}t0,t1;
int a[maxn],val[maxn];
int f[maxn][2],g[maxn][2];
int ans[maxn];
int n;
int check(int cnt0,int mx0,int cnt1,int mx1,int rest)
{
	// printf("%d %d %d %d %d\n",cnt0,mx0,cnt1,mx1,rest);
	if(mx0<n&&cnt1-cnt0+rest>=0){
		if((cnt1-cnt0+rest)&1){
			if(t1.query(1,1,n,mx0+1,n)>=cnt1-cnt0+rest)return 1;
		}
		else if(t0.query(1,1,n,mx0+1,n)>=cnt1-cnt0+rest)return 1;
	}
	if(mx1<n&&cnt0-cnt1+rest>=0){
		if((cnt0-cnt1+rest)&1){
			if(t1.query(1,1,n,mx1+1,n)>=cnt0-cnt1+rest)return 1;
		}
		else if(t0.query(1,1,n,mx1+1,n)>=cnt0-cnt1+rest)return 1;
	}
	return 0;
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)
		a[i]=read();
	t0.build(1,1,n,0); t1.build(1,1,n,-inf);
	int mx=0;
	for(int i=1;i<=n;i++)
		if(a[i]>mx){
			mx=a[i]; val[i]=1;
		}
		else val[i]=0;
	for(int i=n;i;i--){
		if(!val[i]){
			f[i][0]=t1.query(1,1,n,a[i],n)+1;
			f[i][1]=t0.query(1,1,n,a[i],n)+1;
		}
		else{
			f[i][0]=t0.query(1,1,n,a[i],n)+2;
			f[i][1]=t1.query(1,1,n,a[i],n)+2;
		}
		t0.modify(1,1,n,a[i],f[i][0]);
		t1.modify(1,1,n,a[i],f[i][1]);
	}
	// for(int i=1;i<=n;i++)
	// 	printf("%d : %d %d\n",i,f[i][0],f[i][1]);
	int rest=0;
	for(int i=1;i<=n;i++)
		rest+=val[i];
	int cnt0=0,cnt1=0,mx0=0,mx1=0;
	if(!check(cnt0,mx0,cnt1,mx1,rest)){
		puts("-1"); return 0;
	}
	for(int i=1;i<=n;i++){
		t0.modify(1,1,n,a[i],0);
		t1.modify(1,1,n,a[i],-inf);
		// printf("%d %d *****************\n",i,val[i]);
		rest-=val[i];
		if(check(cnt0+(a[i]>mx0),std::max(mx0,a[i]),cnt1,mx1,rest)){
			ans[i]=0;
			cnt0+=(a[i]>mx0); mx0=std::max(mx0,a[i]);
		}
		else{
			ans[i]=1;
			cnt1+=(a[i]>mx1); mx1=std::max(mx1,a[i]);
		}
	}
	for(int i=1;i<=n;i++)
		putchar(ans[i]+'0');
	putchar('\n');
	return 0;
}