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<cstring>
#include<cstdio>
#include<vector>
#include<algorithm>

using namespace std;

#define LL long long
#define fgx cerr<<"--------------"<<endl;
#define dgx cerr<<"=============="<<endl;

inline int read(){
	int x=0,f=1;char c=getchar();
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(;isdigit(c);c=getchar()) x=x*10+c-'0';
	return x*f;
}
const int MAXN = 200010;
const int INF = 2147483600;

int N; int a[MAXN+1]; 
struct Seg{
	int mx[MAXN<<2];
	inline void build(int rt,int l,int r){
		mx[rt]=-1; if(l==r) return ; int mid=(l+r)>>1;
		build(rt<<1,l,mid); build(rt<<1|1,mid+1,r); 
	}
	inline int Query(int rt,int l,int r,int L,int R){
		if(L<=l&&R>=r) return mx[rt]; int mid=(l+r)>>1,ans=-1;
		if(L<=mid) ans=max(ans,Query(rt<<1,l,mid,L,R));
		if(R>mid) ans=max(ans,Query(rt<<1|1,mid+1,r,L,R)); return ans;
	}
	inline void Set(int rt,int l,int r,int k,int n){
		if(l==r) { mx[rt]=n; return ; } int mid=(l+r)>>1;
		if(k<=mid) Set(rt<<1,l,mid,k,n); else Set(rt<<1|1,mid+1,r,k,n);
		mx[rt]=max(mx[rt<<1],mx[rt<<1|1]);
	}
}T0,T1;
int N1;
inline bool Check(int lv,int c){
	if(c<0) return 0;
	if(c&1) return (T1.Query(1,1,N1,lv,N1)>=c);
	else return (T0.Query(1,1,N1,lv,N1)>=c);
} int val[MAXN+1],mx;
int q[MAXN+1],mxa,mxb,la,lb,lena,lenb;
char s[MAXN+1];

int main(){
	//freopen("void.out","r",stdin);
	//freopen(".out","w",stdout);
	N=read(); N1=N+1; int Sum=0;
	for(int i=1;i<=N;i++) {
		val[i]=1; a[i]=read(); mx=max(mx,a[i]);
		if(mx==a[i]) val[i]=2,++Sum;
		q[i]=Sum;
	} T0.build(1,1,N1); T1.build(1,1,N1);
	T0.Set(1,1,N1,N1,0);
	for(int i=N;i>=1;i--){
		int x0=T0.Query(1,1,N1,a[i],N1),x1=T1.Query(1,1,N1,a[i],N1);
		if(val[i]==1){
			if(x0!=-1) T1.Set(1,1,N1,a[i],x0+1); 
			if(x1!=-1) T0.Set(1,1,N1,a[i],x1+1);
		} else{
			if(x1!=-1) T1.Set(1,1,N1,a[i],x1+2); 
			if(x0!=-1) T0.Set(1,1,N1,a[i],x0+2);
		}
	} for(int i=1;i<=N;i++) q[i]=Sum-q[i];
	if((Sum&1)&&T1.Query(1,1,N1,1,N1)<Sum){ puts("-1"); return 0;}
	if(!(Sum&1)&&T0.Query(1,1,N1,1,N1)<Sum){ puts("-1"); return 0; }
	for(int i=1;i<=N;i++){
		T0.Set(1,1,N1,a[i],0); T1.Set(1,1,N1,a[i],-1);
		int tma=max(mxa,a[i]),tmb=max(mxb,a[i]),la=lena,lb=lenb;
		if(tma==a[i]) ++la;
		if(Check(mxb,la+q[i]-lb)||Check(tma,lb+q[i]-la)) {
			s[i]='0'; lena=la; lenb=lb; mxa=tma;
		} else{
			la=lena,lb=lenb; if(tmb==a[i]) ++lb; lena=la; lenb=lb; mxb=tmb;
			s[i]='1';
		}
	} puts(s+1);
	return 0;
}