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 N 2000010
int v[N],n,va[N],mx,c[N];
char s[N];
struct st{
	int mx[N];
	void bd(int o,int l,int r){
		mx[o]=-1e9;
		if(l==r)return;
		int md=(l+r)/2;
		bd(o*2,l,md);
		bd(o*2+1,md+1,r);
	}
	void mod(int o,int l,int r,int x,int y){
		if(l==r){
			mx[o]=y;
			return;
		}
		int md=(l+r)/2;
		if(x<=md)mod(o*2,l,md,x,y);
		else mod(o*2+1,md+1,r,x,y);
		mx[o]=max(mx[o*2],mx[o*2+1]);
	}
	int q(int o,int l,int r,int x,int y){
		if(r<x||y<l)return -1e9;
		if(x<=l&&r<=y)return mx[o];
		int md=(l+r)/2;
		return max(q(o*2,l,md,x,y),q(o*2+1,md+1,r,x,y));
	}
}a,b;
int ck(int x,int v){
	if(v<0)return 0;
	if(v&1)return a.q(1,1,n,x,n)>=v;
	return b.q(1,1,n,x,n)>=v;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		scanf("%d",&v[i]);
		if(v[i]>mx){
			mx=v[i];
			va[i]=2;
		}
		else va[i]=1;
	}
	a.bd(1,1,n);
	for(int i=n;i;i--){
		int m1=a.q(1,1,n,v[i],n),m0=b.q(1,1,n,v[i],n);
		if(va[i]==1){
			a.mod(1,1,n,v[i],m0+1);
			b.mod(1,1,n,v[i],m1+1);
		}
		else{
			a.mod(1,1,n,v[i],m1+2);
			b.mod(1,1,n,v[i],m0+2);
		}
		c[i]=c[i+1]+va[i]-1;
	}
	int cx=0,cy=0,mx=0,my=0;
	for(int i=1;i<=n;i++){
		a.mod(1,1,n,v[i],-1e9);
		b.mod(1,1,n,v[i],0);
		if(ck(my,cx+c[i+1]-cy+(v[i]>mx))){
			s[i]='0';
			cx+=(v[i]>mx);
			mx=max(mx,v[i]);
		}
		else if(ck(max(mx,v[i]),cy+c[i+1]-cx-(v[i]>mx))){
			s[i]='0';
			cx+=(v[i]>mx);
			mx=max(mx,v[i]);
		}
		else{
			s[i]='1';
			cy+=(v[i]>my);
			my=max(my,v[i]);
		}
	}
	if(cx!=cy)puts("-1");
	else cout<<s+1;
}