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;
const int N=200010,inf=1e9;
int n;
int a[N],v[N],cnt,sum[N];
struct seg
{
	int mx[N<<2];
	void init(){memset(mx,-63,sizeof(mx));}
	void pushup(int k){mx[k]=max(mx[k<<1],mx[k<<1|1]);}
	void modify(int p,int x,int l=0,int r=n,int k=1)
	{
		if(l==r){mx[k]=x;return;}
		int mid=l+r>>1;
		if(p<=mid)modify(p,x,l,mid,k<<1);
		else modify(p,x,mid+1,r,k<<1|1);
		pushup(k);
	}
	int query(int L,int R,int l=0,int r=n,int k=1)
	{
		if(L>R)return -inf;
		if(L<=l && r<=R)return mx[k];
		int mid=l+r>>1,res=-inf;
		if(L<=mid)res=max(res,query(L,R,l,mid,k<<1));
		if(R>mid)res=max(res,query(L,R,mid+1,r,k<<1|1));
		return res;
	}
}t[2];
char ans[N];
bool check(int p,int x)
{
	if(x<0)return 0;
	return t[x&1].query(p,n)>=x;
}
int main()
{
	scanf("%d",&n);
	t[1].init();
	int mx=0;
	for(int i=1;i<=n;i++)
	{
		scanf("%d",&a[i]);
		if(a[i]>mx)v[i]=2,cnt++;
		else
			v[i]=1;
		mx=max(mx,a[i]);
	}
	for(int i=n;i;i--)
	{
		int x=t[0].query(a[i],n),y=t[1].query(a[i],n);
		t[v[i]&1].modify(a[i],x+v[i]),t[(v[i]&1)^1].modify(a[i],y+v[i]);
	}
	for(int i=n;i;i--)sum[i]=sum[i+1]+v[i]-1;
	int cntx=0,cnty=0,mxx=0,mxy=0;
	for(int i=1;i<=n;i++)
	{
		t[0].modify(a[i],0); t[1].modify(a[i],-inf);
		if(check(mxy,sum[i+1]+cntx+(a[i]>mxx)-cnty) || check(max(mxx,a[i]),sum[i+1]+cnty-cntx-(a[i]>mxx)))ans[i]='0',cntx+=mxx<a[i],mxx=max(a[i],mxx);
		else
			ans[i]='1',cnty+=mxy<a[i],mxy=max(a[i],mxy);
	}
	if(cntx!=cnty)puts("-1");
	else
		printf("%s",ans+1);
	return 0;
}