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<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<queue>
#include<cmath>
#include<cstdlib>
#define LL long long
#define LD long double
using namespace std;
const int NN=200000 +117;
const int MM=200000 +117;
int read(){
	int fl=1,x;char c;
	for(c=getchar();(c<'0'||c>'9')&&c!='-';c=getchar());
	if(c=='-'){fl=-1;c=getchar();}
	for(x=0;c>='0'&&c<='9';c=getchar())
		x=(x<<3)+(x<<1)+c-'0';
	return x*fl;
}
void open(){
	freopen("a.in","r",stdin);
	//freopen("a.out","w",stdout);
}
void close(){
	fclose(stdin);
	fclose(stdout);
}


int m,n;
bool mark[NN]={};
int suf[NN]={};
struct seg{
	int ev,od;
	int s[2];
}t[30*NN]={};
int tcnt=0;
int a[NN]={};
int rt[NN]={};
int op[NN]={};
void push_up(int pos){
	int ls=t[pos].s[0];
	int rs=t[pos].s[1];
	t[pos].ev=max(t[ls].ev,t[rs].ev);
	t[pos].od=max(t[ls].od,t[rs].od);
}
int build(int l,int r){
	int pos=++tcnt;
	if(l==r){
		t[pos].ev=0;
		t[pos].od=-1e9+1;
		return pos;
	}
	int mid=(l+r)>>1;
	t[pos].s[0]=build(l,mid);
	t[pos].s[1]=build(mid+1,r);
	push_up(pos);
	return pos;
}
int find(int l,int r,int pos,int x,int kd){
	if(l>=x){
		if(kd)return t[pos].od;
		else return t[pos].ev;
	}
	if(r<x)return -1e9;
	int mid=(l+r)>>1;
	int ret=find(l,mid,t[pos].s[0],x,kd);
	ret=max(ret,find(mid+1,r,t[pos].s[1],x,kd));
	return ret;
}
int modify(int l,int r,int pos,int tar,int v1,int v2){
	int cur=++tcnt;
	if(l==r){
		t[cur].ev=v1;
		t[cur].od=v2;
		return cur;
	}
	int mid=(l+r)>>1;
	if(tar<=mid){
		t[cur].s[0]=modify(l,mid,t[pos].s[0],tar,v1,v2);
		t[cur].s[1]=t[pos].s[1];
	}
	else{
		t[cur].s[0]=t[pos].s[0];
		t[cur].s[1]=modify(mid+1,r,t[pos].s[1],tar,v1,v2);
	}
	push_up(cur);
	return cur;
}
bool chk(int h1,int c1,int h2,int c2,int len){
	int t=c1-c2+suf[len+1];
	if(t>=0){
		int res=find(1,n+1,rt[len+1],h2+1,t&1);;
		return res>=t;
	}
	else return false;
}
void preproc(){
	rt[n+1]=build(1,n+1);
	for(int i=n;i>=1;--i){
		int ev=find(1,n+1,rt[i+1],a[i]+1,0);
		int od=find(1,n+1,rt[i+1],a[i]+1,1);
		ev+=1+mark[i];
		od+=1+mark[i];
		if(ev&1)swap(ev,od);
		rt[i]=modify(1,n+1,rt[i+1],a[i],ev,od);
	}
}
int main(){
	//open();
	n=read();
	int pre=-1;
	for(int i=1;i<=n;++i){
		a[i]=read();
		if(a[i]>pre){
			pre=a[i];
			mark[i]=1;
		}
	}
	for(int i=n;i>=1;--i){
		if(mark[i])suf[i]=suf[i+1]+1;
		else suf[i]=suf[i+1];
	}
	preproc();
	int pre1=-1,pre2=-1;
	int pc1=0,pc2=0;
	bool fail=0;
	for(int i=1;i<=n;++i){
		op[i]=0;
		int h1=pre1,h2=pre2,cnt1=pc1,cnt2=pc2;
		if(a[i]>pre1){
			h1=a[i];
			++cnt1;
		}
		if(chk(h1,cnt1,h2,cnt2,i)||chk(h2,cnt2,h1,cnt1,i)){
			pre1=h1,pre2=h2,pc1=cnt1,pc2=cnt2;
			continue;
		}
		op[i]=1;
		h1=pre1,h2=pre2,cnt1=pc1,cnt2=pc2;
		if(a[i]>pre2){
			h2=a[i];
			++cnt2;
		}
		if(chk(h1,cnt1,h2,cnt2,i)||chk(h2,cnt2,h1,cnt1,i)){
			pre1=h1,pre2=h2,pc1=cnt1,pc2=cnt2;
			continue;
		}
		fail=1;
		break;
	}
	if(fail){
		printf("-1\n");
	}
	else{
		for(int i=1;i<=n;++i){
			putchar('0'+op[i]);
		}
		putchar('\n');
	}
	close();
	return 0;
}