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=2e5+10,M=6e6+10;

int n,a[N],val[N],suf[N];
int pos[N][2],mx[2],mn[2][2],le[2][2];
char ans[N];

struct BIT{
	int t[N],tg[M],vl[M],cnt;
	inline void ad(int x,int vv)
	{
		for(;x<=n;x+=(x&(-x))){
			tg[++cnt]=x;vl[cnt]=t[x];
			t[x]=max(t[x],vv);
		}
	}
	inline int get(int x)
	{
		int re=-1e9;
		for(x=min(x,n);x;x-=(x&(-x))) re=max(re,t[x]);
		return re;
	}
	inline void reback(int x){for(;cnt>x;t[tg[cnt]]=vl[cnt--]);}

}bit[2];

int main(){
	scanf("%d",&n);
	int i,j,k,x,y,cur=n+1,ptr,nq=0;
    for(i=1;i<=n;++i){
    	scanf("%d",&a[i]);
    	a[i]=n+1-a[i];
    	if(cur>a[i]){
    		cur=a[i];val[i]=2;
    	}else val[i]=1;
    }
    memset(bit[1].t,0x8f,sizeof(bit[1].t));
    for(i=n;i;--i) suf[i]=suf[i+1]+(val[i]==2);
    for(i=n;i>1;--i){
    	 for(j=0;j<2;++j) mx[j]=max(0,bit[j].get(a[i]));
    	 for(j=0;j<2;++j){
    	 	x=mx[j]+val[i];
    	 	bit[x&1].ad(a[i],x);
    	 }
    	 for(j=0;j<2;++j) pos[i][j]=bit[j].cnt;
    }
    mn[0][0]=mn[0][1]=n+1;
    for(i=1;i<=n;++i){
    	nq^=1;
        if(i<n)	for(j=0;j<2;++j) bit[j].reback(pos[i+1][j]);
		for(j=0;j<2;++j){
			for(k=0;k<2;++k) mn[nq][k]=mn[nq^1][k],le[nq][k]=le[nq^1][k];
    		if(a[i]<mn[nq^1][j]){mn[nq][j]=a[i];le[nq][j]=le[nq^1][j]+1;}
    		ptr= i==n?(le[nq][0]==le[nq][1]):0;
    		if(i<n){
    			for(k=0;k<2;++k){
    				x=le[nq][k]-le[nq][k^1]+suf[i+1];
    				if(x>=0 && x<=bit[x&1].get(mn[nq][k^1])){ptr=1;break;}
    			}
    		}
    		if(ptr){ans[i]='0'+j;break;}
    	}
    	if(!ans[i]){printf("-1");return 0;}
    }
    for(i=1;i<=n;++i) putchar(ans[i]);
    return 0;
}