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<algorithm>
#include<cstring>
#define lson o<<1
#define rson o<<1|1
#define mid (l+r)/2
using namespace std;
int n,p[200005],maxx[200005],v[200005],x[800005][2],f[800005][2],sum[200005];
void pushup(int o)
{
	x[o][0]=max(x[lson][0],x[rson][0]);
	x[o][1]=max(x[lson][1],x[rson][1]);
}
void update(int o,int l,int r,int p,int v0,int v1)
{
	if(l==r)
	{
		x[o][1]=v1;
		x[o][0]=v0;
		return;
	}
	if(p<=mid)update(lson,l,mid,p,v0,v1);
	else update(rson,mid+1,r,p,v0,v1);
	pushup(o);
}
pair<int,int>query(int o,int l,int r,int from,int to)
{
	if(l>=from&&r<=to)return make_pair(x[o][0],x[o][1]);
	pair<int,int>ans=make_pair(0,0),res;
	if(from<=mid)
	{
		res=query(lson,l,mid,from,to);
		if(res.first>ans.first)ans.first=res.first;
		if(res.second>ans.second)ans.second=res.second;
	}
	if(to>mid)
	{
		res=query(rson,mid+1,r,from,to);
		if(res.first>ans.first)ans.first=res.first;
		if(res.second>ans.second)ans.second=res.second;
	}
	return ans;
}
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&p[i]);
		maxx[i]=max(maxx[i-1],p[i]);
		if(maxx[i]==p[i])v[i]=2;
		else v[i]=1;
	}
	for(int i=n;i>=1;i--)
	{
		pair<int,int>res=query(1,1,n,p[i],n);
		if(v[i]&1)
		{
			f[i][0]=res.second+v[i];
			f[i][1]=res.first+v[i];
		}
		else
		{
			f[i][0]=res.first+v[i];
			f[i][1]=res.second+v[i];
		}
		if(f[i][0]&1)f[i][0]=0;
		if(f[i][1]%2==0)f[i][1]=0;
		update(1,1,n,p[i],f[i][0],f[i][1]);
		if(maxx[i]==p[i])sum[i]=sum[i+1]+1;
		else sum[i]=sum[i+1];
	}
	int v1=0,v2=0,m1=0,m2=0;
	for(int i=1;i<=n;i++)
	{
		int vv1=v1+(p[i]>m1);
		int mm1=max(m1,p[i]);
		update(1,1,n,p[i],0,0);
		int g=vv1+sum[i+1]-v2,val;
		pair<int,int>res;
		if(g>=0)
		{
			res=query(1,1,n,min(m2+1,n),n);
			if(g&1)val=res.second;
			else val=res.first;
			if(val>=g)
			{
				printf("0");
				if(p[i]>m1)v1++,m1=p[i];
				continue;
			}
		}
		g=v2+sum[i+1]-vv1;
		if(g>=0)
		{
			res=query(1,1,n,min(mm1+1,n),n);
			if(g&1)val=res.second;
			else val=res.first;
			if(val>=g)
			{
				printf("0");
				if(p[i]>m1)v1++,m1=p[i];
				continue;
			}
		}
		if(i==1)
		{
			printf("-1\n");
			return 0;
		}
		printf("1");
		if(p[i]>m2)v2++,m2=p[i];
	}
	printf("\n");
	return 0;
}