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 <iostream>
#include <cstdio>
#define N 200002
using namespace std;
int n,i,p[N],a[N],q[N],s[N],t[2][N*4];
int read()
{
	char c=getchar();
	int w=0;
	while(c<'0'||c>'9') c=getchar();
	while(c<='9'&&c>='0'){
		w=w*10+c-'0';
		c=getchar();
	}
	return w;
}
void build(int p,int l,int r)
{
	t[1][p]=-1<<30;
	if(l==r) return;
	int mid=(l+r)/2;
	build(p*2,l,mid);build(p*2+1,mid+1,r);
}
void change(int op,int p,int l,int r,int x,int v)
{
	if(l==r){
		t[op][p]=v;
		return;
	}
	int mid=(l+r)/2;
	if(x<=mid) change(op,p*2,l,mid,x,v);
	else change(op,p*2+1,mid+1,r,x,v);
	t[op][p]=max(t[op][p*2],t[op][p*2+1]);
}
int ask(int op,int p,int l,int r,int ql,int qr)
{
	if(ql<=l&&r<=qr) return t[op][p];
	int mid=(l+r)/2,ans=-1<<30;
	if(ql<=mid) ans=max(ans,ask(op,p*2,l,mid,ql,qr));
	if(qr>mid) ans=max(ans,ask(op,p*2+1,mid+1,r,ql,qr));
	return ans;
}
bool check(int x,int y)
{
	if(y<0) return 0;
	if(y%2==0) return (ask(0,1,1,n,x,n)>=y);
	else return (ask(1,1,1,n,x,n)>=y);
}
int main()
{
	n=read();
	for(i=1;i<=n;i++) p[i]=read();
	int maxp=0;
	for(i=1;i<=n;i++){
		maxp=max(maxp,p[i]);
		if(p[i]==maxp) a[i]=2;
		else a[i]=1;
	}
	for(i=n;i>=1;i--) q[i]=q[i+1]+a[i]-1;
	build(1,1,n);
	for(i=n;i>=1;i--){
		int tmp0=ask(0,1,1,n,p[i],n)+a[i],tmp1=ask(1,1,1,n,p[i],n)+a[i];
		if(a[i]%2==0) change(0,1,1,n,p[i],tmp0),change(1,1,1,n,p[i],tmp1);
		else change(0,1,1,n,p[i],tmp1),change(1,1,1,n,p[i],tmp0);
	}
	int cntx=0,cnty=0,maxx=0,maxy=0;
	for(i=1;i<=n;i++){
		change(0,1,1,n,p[i],0);
		change(1,1,1,n,p[i],-1<<30);
		if(check(maxy,cntx+(p[i]>maxx)+q[i+1]-cnty)||check(max(maxx,p[i]),cnty+q[i+1]-cntx-(p[i]>maxx))){
			cntx+=(p[i]>maxx);
			maxx=max(maxx,p[i]);
		}
		else{
			s[i]=1;
			cnty+=(p[i]>maxy);
			maxy=max(maxy,p[i]);
		}
	}
	if(cntx!=cnty) puts("-1");
	else{
		for(i=1;i<=n;i++) printf("%d",s[i]);
		puts("");
	}
	return 0;
}