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<cmath>
#include<cstring>
#include<algorithm>
#define maxn 200005
using namespace std;

int n,i,j,k,a[maxn];

struct segmenttree{
	int t[maxn*4],inf;
	void maketree(int x,int l,int r){
		t[x]=inf; if (l==r) return;
		int mid=(l+r)>>1;
		maketree(x<<1,l,mid),maketree(x<<1^1,mid+1,r);
	}
	int find(int x,int l,int r,int L,int R){
		if (l>R||r<L) return inf;
		if (L<=l&&r<=R) return t[x];
		int mid=(l+r)>>1;
		return max(find(x<<1,l,mid,L,R),find(x<<1^1,mid+1,r,L,R));
	}
	void change(int x,int l,int r,int p,int v){
		if (l==r) {t[x]=max(v,inf);return;}
		int mid=(l+r)>>1;
		if (p<=mid) change(x<<1,l,mid,p,v);
		else change(x<<1^1,mid+1,r,p,v);
		t[x]=max(t[x<<1],t[x<<1^1]);
	}
} t[2];

int bz[maxn],Q[maxn];
void prepare(){
	t[0].inf=0,t[1].inf=-1e9;
	t[0].maketree(1,1,n),t[1].maketree(1,1,n);
	int mx=0;
	for(i=1;i<=n;i++) mx=max(mx,a[i]),bz[i]=(a[i]==mx)+1;
	for(i=n;i>=1;i--) Q[i]=Q[i+1]+bz[i]-1;
	for(i=n;i>=1;i--) for(j=0;j<2;j++)
		t[j^(bz[i]&1)].change(1,1,n,a[i],t[j].find(1,1,n,a[i]+1,n)+bz[i]);
}

void clear(int i){
	t[0].change(1,1,n,a[i],t[0].inf);
	t[1].change(1,1,n,a[i],t[1].inf);
}

int s[maxn],lena,lenb,mxa,mxb;
int check(int i,int la,int lb,int ma,int mb){
	if (la-lb+Q[i]>=0&&t[(la-lb+Q[i])&1].find(1,1,n,mb+1,n)>=la-lb+Q[i])
		return 1;
	if (lb-la+Q[i]>=0&&t[(lb-la+Q[i])&1].find(1,1,n,ma+1,n)>=lb-la+Q[i])	
		return 1;
	return 0;
}

void doit(){
	lena=lenb=mxa=mxb=0;
	clear(1);
	if (!check(1,lena,lenb,mxa,mxb))
		printf("-1"),exit(0);
	for(i=1;i<=n;i++){
		if (check(i+1,lena+(a[i]>mxa),lenb,max(mxa,a[i]),mxb))
			s[i]=0,lena+=a[i]>mxa,mxa=max(mxa,a[i]); else 
			s[i]=1,lenb+=a[i]>mxb,mxb=max(mxb,a[i]);
		if (i<n) clear(i+1);
	}
}

int main(){
	scanf("%d",&n);
	for(i=1;i<=n;i++) scanf("%d",&a[i]);
	prepare();
	doit();
	for(i=1;i<=n;i++) putchar('0'+s[i]);
}