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>
using namespace std;
int gi(){
	int x=0,w=1;char ch=getchar();
	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
	if(ch=='-')w=0,ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
const int N=2e5+5;
int n,q,a[N],b[N];
struct fenwick{
	int c[N],top,tt[N];pair<int,int>S[N*20];
	void init(int v){
		for(int i=1;i<=n;++i)c[i]=v;
	}
	void modify(int x,int v){
		while(x<=n){
			if(c[x]<v)S[++top]=make_pair(x,c[x]),c[x]=v;
			x+=x&-x;
		}
	}
	void rollback(int i){
		while(top>tt[i])c[S[top].first]=S[top].second,--top;
	}
	int query(int x){
		int res=-1<<30;
		while(x)res=max(res,c[x]),x^=x&-x;
		return res;
	}
}foo,bar;
bool check(int x,int v){
	if(v<0)return false;
	if(v&1)return foo.query(n+1-x)>=v;
	else return bar.query(n+1-x)>=v;
}
bool check(int max0,int max1,int dif){
	return check(max0,q-dif)||check(max1,q+dif);
}
int main(){
	n=gi();
	for(int i=1,pre_max=0;i<=n;++i){
		a[i]=gi();
		if(a[i]>pre_max){
			pre_max=a[i];
			b[i]=1;++q;
		}
	}
	foo.init(-1<<30);bar.init(0);
	for(int i=n;i;--i){
		int x=-1<<30,y=-1<<30;
		if(b[i]){
			x=foo.query(n+1-a[i])+2;
			y=bar.query(n+1-a[i])+2;
		}else{
			x=bar.query(n+1-a[i])+1;
			y=foo.query(n+1-a[i])+1;
		}
		foo.tt[i]=foo.top;foo.modify(n+1-a[i],x);
		bar.tt[i]=bar.top;bar.modify(n+1-a[i],y);
	}
	if(!check(1,q))return puts("-1"),0;
	for(int i=1,max0=1,max1=1,dif=0;i<=n;++i){
		if(b[i])--q;
		foo.rollback(i);bar.rollback(i);
		if(a[i]>=max0)
			if(check(a[i],max1,dif+1))
				putchar('0'),max0=a[i],++dif;
			else
				putchar('1'),dif-=a[i]>=max1,max1=max(max1,a[i]);
		else
			if(check(max0,max1,dif))
				putchar('0');
			else
				putchar('1'),dif-=a[i]>=max1,max1=max(max1,a[i]);
	}
	puts("");return 0;
}