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<vector>
#include<cmath>
#include<map>
#include<cstdlib>
#include<iostream>
#include<sstream>
#include<fstream>
#include<string>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<set>
#include<stack>
#include<bitset>
#include<functional>
#include<ctime>
#include<queue>
#include<deque>
#include<complex>
#include<cassert>
using namespace std;
#define pb push_back
#define pf push_front
typedef long long lint;
typedef complex<double> P;
#define mp make_pair
#define fi first
#define se second
typedef pair<int,int> pint;
#define All(s) s.begin(),s.end()
#define rAll(s) s.rbegin(),s.rend()
#define REP(i,a,b) for(int i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
//問題文および制約はちゃんと確認しよう！
//サイズは10^5じゃなくて2×10^5とかかもしれないし、重要な制約・条件を見落としているかも
//とりあえずサンプルを読んでから解法を考えよう？
#define N 262144
int dat[2][N*2+10];
int inf=1000000000;
int query(int a,int b,int id,int k=0,int l=0,int r=N){
	if(r<=a || b<=l) return -inf;
	if(a<=l && r<=b) return dat[id][k];
	int vl=query(a,b,id,k*2+1,l,(l+r)/2);
	int vr=query(a,b,id,k*2+2,(l+r)/2,r);
	return max(vl,vr);
}
void update(int id,int k,int a){
	k+=N-1;
	dat[id][k]=a;
	while(k>0){
		k=(k-1)/2;
		dat[id][k]=max(dat[id][k*2+1],dat[id][k*2+2]);
	}
	return;
}
int a[N];
bool hi[N];int n;
bool ok(int hx,int hy,int nx,int ny,int nh){
	//cout<<hx<<hy<<nx<<ny<<nh<<endl;
	//x側でやる場合
	int target=ny+nh-nx;
	if(target>=0 && query(hx+1,n+10,(target&1))>=target) return true;
	//y側でやる場合
	target=nx+nh-ny;
	if(target>=0 && query(hy+1,n+10,(target&1))>=target) return true;
	return false;
}
int main()
{
	cin>>n;
	rep(i,n) cin>>a[i];
	int h=0,nh=0;
	rep(i,n){
		if(a[i]>h) hi[i]=true,h=a[i],nh++;
	}
	rep(i,N*2+5) dat[0][i]=dat[1][i]=-inf;
	update(0,n+5,0);
	for(int i=n-1;i>=0;i--){
		if(hi[i]){
			update(0,a[i],query(a[i]+1,n+10,0)+2);
			update(1,a[i],query(a[i]+1,n+10,1)+2);
		}
		else{
			update(0,a[i],query(a[i]+1,n+10,1)+1);
			update(1,a[i],query(a[i]+1,n+10,0)+1);
		}
	}
	//REP(i,1,n+1) cout<<query(i,i+1,0)<<" "<<query(i,i+1,1)<<endl;
	int hx=0,hy=0,nx=0,ny=0;
	if(!ok(hx,hy,nx,ny,nh)){
		cout<<-1<<endl;return 0;
	}
	string out="";
	rep(i,n){
		//cout<<hx<<hy<<nx<<ny<<nh<<endl;
		update(0,a[i],-inf);update(1,a[i],-inf);
		//setx
		int nhx=max(hx,a[i]),nnx=nx+(a[i]>hx);
		nh-=hi[i];
		if(ok(nhx,hy,nnx,ny,nh)){
			out+="0";hx=nhx;nx=nnx;
		}
		else{
			out+="1";ny+=(a[i]>hy);hy=max(hy,a[i]);
		}
	}
	cout<<out<<endl;
}