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,n) for ((i)=1;(i)<=(n);(i)++)
using namespace std;
int n,a[200005],i,j,mx,num,b[200005],ed[200005][2];
struct bit{
	int a[200005];
	vector<int> pos,mem;
	void add(int x,int y){
		while(x){
			pos.push_back(x);
			mem.push_back(a[x]);
			a[x]=max(a[x],y);
			x-=(x&-x);
		}
	}
	int qry(int x){
		int ans=-0x3f3f3f3f;
		while(x<=n){
			ans=max(ans,a[x]);
			x+=(x&-x);
		}return ans;
	}
	void undo(){
		a[pos.back()]=mem.back();
		pos.pop_back();
		mem.pop_back();
	}
}t[2];
int main(){
	cin>>n;
	rep(i,n){
		cin>>a[i];
		if(a[i]>mx){
			mx=a[i];
			num++;
			b[i]=2;
		}
		else{
			b[i]=1;
		}
	}
	memset(t[1].a,-0x3f,sizeof(t[1].a));
	for(i=n;i;i--){
		int s0=t[0].qry(a[i]),s1=t[1].qry(a[i]);
		if(s0+b[i]<=num) t[(s0+b[i])&1].add(a[i],s0+b[i]);
		if(s1+b[i]<=num) t[(s1+b[i])&1].add(a[i],s1+b[i]);
		ed[i][0]=t[0].pos.size();
		ed[i][1]=t[1].pos.size();
	}
	if(t[num&1].qry(1)!=num){
		puts("-1");
		return 0;
	}
	int mx0=0,mx1=0,cnt0=0,cnt1=0;
	rep(i,n){
		while(t[0].pos.size()>ed[i+1][0]){
			t[0].undo();
		}
		while(t[1].pos.size()>ed[i+1][1]){
			t[1].undo();
		}
		int nmx1=mx1,ncnt1=cnt1;
		if(a[i]>nmx1){
			nmx1=a[i];
			ncnt1++;
		}
		num-=(b[i]==2);
		if((num+cnt0-ncnt1>=0&&t[(num+cnt0-ncnt1)&1].qry(nmx1)>=num+cnt0-ncnt1)||
		   (num-cnt0+ncnt1>=0&&t[(num-cnt0+ncnt1)&1].qry(max(1,mx0))>=num-cnt0+ncnt1)){
				putchar('0');
				mx1=nmx1;
				cnt1=ncnt1;
		}
		else{
				putchar('1');
				if(a[i]>mx0){
					mx0=a[i];
					cnt0++;
				}
		}
	}
	puts("");
	return 0;
}