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;
#define Set(a,b) memset(a,b,sizeof(a))
template<class T>inline void init(T&x){
	x=0;char ch=getchar();bool t=0;
	for(;ch>'9'||ch<'0';ch=getchar()) if(ch=='-') t=1;
	for(;ch>='0'&&ch<='9';ch=getchar()) x=(x<<1)+(x<<3)+(ch-48);
	if(t) x=-x;return;
}typedef long long ll;
const int N=2e5+10;
int P[N],sMx[N],hsum[N],Is[N];
int f[N][2];
int tr[2][N],n;
#define lowbit(a) ((a)&(-a))
inline void Update(int*tr,int p,int x){p=n-p+1;for(;p<=n;p+=lowbit(p)) tr[p]=max(tr[p],x);return;}
inline int  Query(int*tr,int p){p=n-p+1;int ret=0;for(;p;p-=lowbit(p)) ret=max(ret,tr[p]);return ret;}
int Mx[2][N<<2];
#define ls (u<<1)
#define rs (u<<1|1)
const int INF=1e9;
inline void Insert(int u,int l,int r,int i,int p){
	Mx[0][u]=max(Mx[0][u],f[i][0]);
	if(!Mx[1][u]) Mx[1][u]=f[i][1];
	else Mx[1][u]=max(Mx[1][u],f[i][1]);
	if(l==r) return;
	int mid=(l+r)>>1;
	if(mid>=p) Insert(ls,l,mid,i,p);
	else       Insert(rs,mid+1,r,i,p);
}
inline void update(int u){Mx[0][u]=max(Mx[0][ls],Mx[0][rs]),Mx[1][u]=max(Mx[1][ls],Mx[1][rs]);}
inline void Del(int u,int l,int r,int p){
	if(l==r) {Mx[0][u]=0,Mx[1][u]=-INF;return;}
	int mid=(l+r)>>1;
	if(mid>=p) Del(ls,l,mid,p);
	else       Del(rs,mid+1,r,p);
	update(u);
}
int Query(int u,int l,int r,int p,int fl){
	if(Mx[fl][u]==-INF) return -INF;
	if(p>r) return -INF;
	if(l>=p) return Mx[fl][u];
	int mid=(l+r)>>1;int re=-INF;
	if(mid>=p) re=max(re,Query(ls,l,mid,p,fl));
	re=max(re,Query(rs,mid+1,r,p,fl));
	return re;
}
char ans[N];
inline bool check(int i,int cntx,int cnty,int maxx,int maxy){
	if(i==n) return cntx==cnty;
	//cerr<<"check : ";cerr<<cntx<<' '<<cnty<<' '<<maxx<<' '<<maxy<<endl;
	int p=hsum[n]-hsum[i];
	int val=cntx-cnty+p,re;
	if(val>=0){
		if(val%2==0) re=Query(1,1,n,maxy+1,0);
		else         re=Query(1,1,n,maxy+1,1);
		//cerr<<"p="<<p<<"  goal_val1="<<val<<"  result1="<<re<<endl;
		if(re>=val) return 1;
	}
	val=cnty-cntx+p;
	if(val>=0){
		if(val%2==0) re=Query(1,1,n,maxx+1,0);
		else         re=Query(1,1,n,maxx+1,1);
		//cerr<<"p="<<p<<"  goal_val2="<<val<<"  result2="<<re<<endl;
		if(re>=val) return 1;
	}
	return 0;
}
int main()
{
	init(n);
	for(int i=1;i<=n;++i) {
		init(P[i]),sMx[i]=max(sMx[i-1],P[i]);
		hsum[i]=hsum[i-1]+(Is[i]=(int)(sMx[i]==P[i]));
	}
	for(int i=n;i;--i) {
		if(Is[i]) {
			f[i][0]=Query(tr[0],P[i])+2;
			f[i][1]=Query(tr[1],P[i])+2;
		}else{
			f[i][0]=Query(tr[1],P[i])+1;
			f[i][1]=Query(tr[0],P[i])+1;
		}
		if(!(f[i][1]&1)) f[i][1]=-INF;
		if(f[i][0]&1) f[i][0]=-INF;
		Update(tr[0],P[i],f[i][0]);
		Update(tr[1],P[i],f[i][1]);
	}
	for(int i=1;i<=n;++i) Insert(1,1,n,i,P[i]);
	int cntx=0,cnty=0;int maxx=0,maxy=0;
	for(int i=1;i<=n;++i) {
		Del(1,1,n,P[i]);
		if(check(i,cntx+(P[i]>maxx),cnty,max(maxx,P[i]),maxy)) ans[i]='0',cntx+=P[i]>maxx,maxx=max(maxx,P[i]);
		else if(check(i,cntx,cnty+(P[i]>maxy),maxx,max(P[i],maxy))) ans[i]='1',cnty+=P[i]>maxy,maxy=max(maxy,P[i]);
		else return puts("-1"),0;
		//puts(ans+1);
	}
	puts(ans+1);
	return 0;
}