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(int i=a,_e=b;i<=_e;++i)
#define fd(i,a,b)for(int i=b,_e=a;i>=_e;--i)
using namespace std;
const int N=2e5+5;
int n,p[N],mx,ct[N],ts,rt[N],an[2];
char ans[N];
struct nod{int l,r,mx[2];}t[N*19];
void qu(int v,int l,int r,int x){
	if(x<=l||!v){
		fo(o,0,1)an[o]=max(an[o],t[v].mx[o]);
		return;
	}
	int m=l+r>>1;
	if(x<=m){
		fo(o,0,1)an[o]=max(an[o],t[t[v].r].mx[o]);
		qu(t[v].l,l,m,x);
	}else qu(t[v].r,m+1,r,x);
}
void ch(int &v,int l,int r,int x){
	t[++ts]=t[v];v=ts;
	fo(o,0,1)t[v].mx[o]=max(t[v].mx[o],an[o]);
	if(l==r)return;
	int m=l+r>>1;
	if(x<=m)ch(t[v].l,l,m,x);else ch(t[v].r,m+1,r,x);
}
bool ck2(int cx,int cy,int hx,int hy,int i){
	int a=cx-cy+ct[i];
	if(a<0)return 0;
	an[0]=an[1]=0;
	if(hy<n)qu(rt[i],1,n,hy+1);
	return a<=an[a&1];
}
bool ck(int cx,int cy,int hx,int hy,int i){
	if(ck2(cx,cy,hx,hy,i)||ck2(cy,cx,hy,hx,i))return 1;
	return 0;
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n;
	fo(i,1,n)cin>>p[i],(mx<p[i]?ct[i]=1,mx=p[i]:0);
	fd(i,1,n){
		rt[i]=rt[i+1];
		an[0]=an[1]=0;
		if(p[i]<n)qu(rt[i],1,n,p[i]+1);
		if(ct[i])an[0]+=2,an[1]+=2;
		else swap(an[0],an[1]),++an[0],++an[1];
		if(an[0]&1)an[0]=0;
		if(~an[1]&1)an[1]=0;
		ch(rt[i],1,n,p[i]);
		ct[i]+=ct[i+1];
	}
	int cx=0,cy=0,hx=0,hy=0;
	fo(i,1,n){
		if(ck(cx+(hx<p[i]),cy,max(hx,p[i]),hy,i+1)){
			if(p[i]>hx)++cx,hx=p[i];
			ans[i]='0';
			continue;
		}
		if(ck(cx,cy+(hy<p[i]),hx,max(hy,p[i]),i+1)){
			if(p[i]>hy)++cy,hy=p[i];
			ans[i]='1';
			continue;
		}
		return puts("-1"),0;
	}
	fo(i,1,n)putchar(ans[i]);
}