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 rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define REP(i,n) for(int i=0;i<(n);i++)
using namespace std;

const int N=200005;
struct node{
	int a,b;
	node(int _a=0,int _b=0){
		if(!(_a&1))_a=0;
		if(_b&1)_b=0;
		a=_a,b=_b;
	}
	friend node operator + (node x,node y){
		return node(max(x.a,y.a),max(x.b,y.b));
	}
}T[N<<2];
int a[N],s[N],H[2],C[2];
char ans[N];
int n,mx;

#define lc (o<<1)
#define rc (o<<1|1)
#define mid ((l+r)>>1)
void upd(int o,int l,int r,int x,node y){
	if(l==r)return (void)(T[o]=y);
	if(x<=mid)upd(lc,l,mid,x,y);
	else upd(rc,mid+1,r,x,y);
	T[o]=T[lc]+T[rc];
}
node qry(int o,int l,int r,int x,int y){
	if(l==x&y==r)return T[o];
	if(y<=mid)return qry(lc,l,mid,x,y);
	if(mid<x)return qry(rc,mid+1,r,x,y);
	return qry(lc,l,mid,x,mid)+qry(rc,mid+1,r,mid+1,y);
}

int chk(int x,int val){
	node ret=qry(1,1,n,max(1,a[x]),n);
	int t[2]={ret.b,ret.a};
	return val>=0&&t[val&1]>=val;
}

int main(){
	scanf("%d",&n);
	rep(i,1,n){
		scanf("%d",&a[i]);
		mx=max(mx,a[i]);
		s[i]=(a[i]==mx);
	}
	per(i,n,1){
		node ret=qry(1,1,n,a[i],n);
		if(s[i]==1)upd(1,1,n,a[i],node(ret.a+2,ret.b+2));
		else upd(1,1,n,a[i],node(ret.b+1,ret.a+1));
		s[i]+=s[i+1];
	}
	if(!chk(0,s[1]))return puts("-1"),0;
	rep(i,1,n){
		int nH=(a[i]>a[H[0]]?i:H[0]);
		int nC=C[0]+(i==nH);
		upd(1,1,n,a[i],node(0,0));
		if(chk(nH,C[1]-nC+s[i+1])||chk(H[1],nC-C[1]+s[i+1]))
			H[0]=nH,C[0]=nC,ans[i]='0';
		else
			H[1]=(a[i]>a[H[1]]?i:H[1]),C[1]+=(i==H[1]),ans[i]='1';
	}
	puts(ans+1);
	return 0;
}