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>
#define stt static
#define rg register
#define ll long long
#define db double
#define pii pair<int,int>
#define mp make_pair
#define fst first
#define snd second
#define pb push_back
#define y1 substitute_of_y1
#define DEBUG(...) fprintf(stderr,__VA_ARGS__)
using namespace std;

template<typename T> T rd(){
	T nmb=0;int sgn=0;char chr=getchar();
	while(!isdigit(chr)){if(chr=='-')sgn=1;chr=getchar();}
	while(isdigit(chr)){nmb=(nmb<<3)+(nmb<<1)+chr-'0';chr=getchar();}
	return sgn?-nmb:nmb;
}
template<typename T> void wt(T nmb){
	if(nmb>9)wt(nmb/10);
	putchar(nmb%10+'0');
}
template<typename T> void cmax(T &x,T y){x=x>y?x:y;}
template<typename T> void cmin(T &x,T y){x=x<y?x:y;}
void proc_status(){
	ifstream t ("/proc/self/status");
	cerr<<string(istreambuf_iterator<char>(t),istreambuf_iterator<char>())<<endl;
	/*freopen("/proc/self/status","r",stdin);
	char ch[100];
	while(scanf("%s",ch)!=EOF)cerr<<ch<<endl;*/
}

const int N=2e5+10;
const int inf=1e9;

int n;
int a[N],mx[N],sum[N];

struct SGT{
	int rt[N];
	int val[N*25],lc[N*25],rc[N*25],cnt;
	void build(int &r,int x,int y){
		r=++cnt;
		val[r]=-inf;
		if(x==y)return;
		int m=(x+y)>>1;
		build(lc[r],x,m);
		build(rc[r],m+1,y);
	}
	void add(int &r1,int r2,int x,int y,int k,int p){
		r1=++cnt;
		lc[r1]=lc[r2],rc[r1]=rc[r2];
		if(x==y){
			val[r1]=max(val[r2],p);
			return;
		}
		int m=(x+y)>>1;
		if(k<=m)add(lc[r1],lc[r2],x,m,k,p);
		else add(rc[r1],rc[r2],m+1,y,k,p);
		val[r1]=max(val[lc[r1]],val[rc[r1]]);
	}
	int query(int r,int x,int y,int u,int v){
		if(u>v)return -inf;
		if(u<=x&&y<=v)return val[r];
		int m=(x+y)>>1,res=-inf;
		if(u<=m)res=query(lc[r],x,m,u,v);
		if(m<v)cmax(res,query(rc[r],m+1,y,u,v));
		return res;
	}
}ver[2];

bool check(int i,int mx1,int mx2,int cnt1,int cnt2){
	int val=cnt1+sum[i+1]-cnt2;
	int res=ver[val&1].query(ver[val&1].rt[i+1],1,n,mx2+1,n);
	if(val>=0&&res>=val)return 1;
	val=cnt2+sum[i+1]-cnt1;
	res=ver[val&1].query(ver[val&1].rt[i+1],1,n,mx1+1,n);
	if(val>=0&&res>=val)return 1;
	return 0;
}

int S[N];

void Init(){
	n=rd<int>();
	for(int i=1;i<=n;++i)
		a[i]=rd<int>();
	for(int i=1;i<=n;++i)
		mx[i]=max(mx[i-1],a[i]);
	for(int i=n;i;--i)
		sum[i]=sum[i+1]+(a[i]==mx[i]);
	ver[1].build(ver[1].rt[n+1],1,n);
	for(int i=n;i;--i){
		int q0=ver[0].query(ver[0].rt[i+1],1,n,a[i],n);//查询[a[i],n]而非[a[i]+1,n]是防止出现u>v的情况, 这种情况下有时需要return 0, 有时需要return -inf
		int q1=ver[1].query(ver[1].rt[i+1],1,n,a[i],n);
		if(a[i]==mx[i])
			ver[0].add(ver[0].rt[i],ver[0].rt[i+1],1,n,a[i],q0+2),
			ver[1].add(ver[1].rt[i],ver[1].rt[i+1],1,n,a[i],q1+2);
		else
			ver[0].add(ver[0].rt[i],ver[0].rt[i+1],1,n,a[i],q1+1),
			ver[1].add(ver[1].rt[i],ver[1].rt[i+1],1,n,a[i],q0+1);
	}
}

void Solve(){
	int Mx1=0,Mx2=0,Cnt1=0,Cnt2=0;
	for(int i=1;i<=n;++i){
		int mx1=max(Mx1,a[i]),mx2=Mx2,cnt1=Cnt1+(a[i]>Mx1),cnt2=Cnt2;
		if(check(i,mx1,mx2,cnt1,cnt2)){
			S[i]=0;
			Mx1=mx1,Mx2=mx2,Cnt1=cnt1,Cnt2=cnt2;
			continue;
		}
		mx1=Mx1,mx2=max(Mx2,a[i]),cnt1=Cnt1,cnt2=Cnt2+(a[i]>Mx2);
		if(check(i,mx1,mx2,cnt1,cnt2)){
			S[i]=1;
			Mx1=mx1,Mx2=mx2,Cnt1=cnt1,Cnt2=cnt2;
			continue;
		}
		puts("-1");exit(0);
	}
	for(int i=1;i<=n;++i)
		printf("%d",S[i]);
	puts("");
}

int main(){
	Init();
	Solve();
	return 0;
}