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 fo(i,a,b) for(i=a;i<=b;i++)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define min(a,b) (a<b?a:b)
#define max(a,b) (a>b?a:b)
using namespace std;
const int maxn=2e5+5;
int i,j,n,p[maxn],mx,Cx,Cy,Hx,Hy,Q;
int f[maxn][2],f0,f1,tr[2][maxn<<2];
bool bz[maxn],ans[maxn];
void cmax(int &x,int y){x=max(x,y);}
void find(int o,int k,int l,int r,int x){
	if (mx>=tr[o][k]) return;
	if (l==r) {mx=tr[o][k];return;}
	int m=(l+r)>>1,lk=k<<1,rk=lk+1;
	if (x<=m) cmax(mx,tr[o][rk]),find(o,lk,l,m,x);else find(o,rk,m+1,r,x);
}
void ins(int k,int l,int r,int x){
	if (l==r) {tr[0][k]=f0,tr[1][k]=f1;return;}
	int m=(l+r)>>1,lk=k<<1,rk=lk+1;
	if (x<=m) ins(lk,l,m,x);else ins(rk,m+1,r,x);
	tr[0][k]=max(tr[0][lk],tr[0][rk]);
	tr[1][k]=max(tr[1][lk],tr[1][rk]);
}
bool check(){
	int T=Cx-Cy+Q;
	if (T>=0){
		mx=0,find(T&1,1,1,n,Hy);
		if (mx>=T) return 1;
	}
	T=Cy-Cx+Q;
	if (T>=0){
		mx=0,find(T&1,1,1,n,Hx);
		return mx>=T;
	}return 0;
}
int main(){
	scanf("%d",&n);
	fo(i,1,n) {
		scanf("%d",&p[i]);
		cmax(mx,p[i]),Q+=(bz[i]=p[i]==mx);
	}
	fd(i,n,1){
		mx=0,find(0,1,1,n,p[i]);
		if (bz[i]) f[i][0]=mx+2;else f[i][1]=mx+1;
		mx=0,find(1,1,1,n,p[i]);
		if (bz[i]) f[i][1]=mx?mx+2:0;else f[i][0]=mx?mx+1:0;
		f0=f[i][0],f1=f[i][1];
		ins(1,1,n,p[i]);
	}
	Hx=Hy=-1,f0=f1=0;
	fo(i,1,n){
		int cx=Cx,cy=Cy,hx=Hx,hy=Hy,x=p[i];
		Q-=bz[i];
		ins(1,1,n,x);
		if (x>Hx) Hx=x,Cx++;
		if (check()) continue;
		Hx=hx,Cx=cx,ans[i]=1;
		if (x>Hy) Hy=x,Cy++;
		if (!check()) break;
	}
	if (i<=n) puts("-1");else
	fo(i,1,n) putchar(48+ans[i]);
}