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 mp make_pair
#define fi first
#define se second
#define ref(i,x,y)for(int i=x;i<=y;++i)
#define def(i,x,y)for(int i=x;i>=y;--i)
#define eef(i,x)for(int i=head[x],y=e[i].to;y;i=e[i].next,y=e[i].to)
int read(){char c=getchar();int d=0,f=1;for(;c<'0'||c>'9';c=getchar())if(c=='-')f=-1;for(;c>='0'&&c<='9';d=d*10+c-48,c=getchar());return d*f;}
char Read(){char c=getchar();while(c<'a'||c>'z')c=getchar();return c;}
typedef pair<int,int>PII;
typedef long long LL;
const double pi=acos(-1);
const int N=200001;
int n, mx, p[N], w[N], f[N][2], hz[N];
int t[N][2], ans[N];
int ask(int id,int x){int s=0;
	for(;x<=n;x+=x&-x)s=max(s,t[x][id]);return s;
}
vector<pair<PII,int> > op[N];int opid;
void upd(int id,int x,int s){
	for(;x>=1;x-=x&-x)if(s>t[x][id]){
		op[opid].push_back(mp(mp(x,id), t[x][id]));
		t[x][id]=s;
	}
}
bool check(int sx,int px,int sy,int py,int x){
	int S1=ask(1,p[py]+1),S0=ask(0,p[py]+1);
	if(sy<=sx+hz[x]&&sy+S1>=sx+hz[x])return 1;
	if(sy<=sx+hz[x]&&sy+S0>=sx+hz[x]&&(sy+S0)%2==(sx+hz[x])%2)return 1;
	S1=ask(1,p[px]+1),S0=ask(0,p[px]+1);
	if(sx<=sy+hz[x]&&sx+S1>=sy+hz[x])return 1;
	if(sx<=sy+hz[x]&&sx+S0>=sy+hz[x]&&(sx+S0)%2==(sy+hz[x])%2)return 1;
	return 0;
}
int main(){
	n=read();
	ref(i,1,n)p[i]=read(),w[i]=1;
	ref(i,1,n)if(p[i]>mx)mx=p[i],w[i]++;
	def(i,n,1)hz[i]=hz[i+1]+w[i]-1;
	def(i,n,0){
		if(w[i]==2) f[i][0]=ask(0,p[i]+1)+w[i];
		f[i][1]=ask(1,p[i]+1);if(f[i][1])f[i][1]+=w[i];
		if(w[i]==1) f[i][1]=max(f[i][1],ask(0,p[i]+1)+w[i]);
		if(i){
			opid=i;
			upd(0,p[i],f[i][0]);
			upd(1,p[i],f[i][1]);
		}
	}
	int sx=0,px=0,sy=0,py=0;
	if(!check(sx,px,sy,py,1)){
		printf("-1\n");
		return 0;
	}
	ref(i,1,n){
		if(!op[i].empty())def(j,op[i].size()-1,0){
			PII u=op[i][j].fi; int v=op[i][j].se;
			t[u.fi][u.se]=v;
		}
		int Sx=sx,Px=px;
		if(p[i]>p[px])Sx++,Px=i;
		if(check(Sx,Px,sy,py,i+1))sx=Sx,px=Px;
		else{
			if(p[i]>p[py])sy++,py=i;
			ans[i]=1;
		}
	}
	ref(i,1,n)printf("%d",ans[i]);
	printf("\n");
}