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>
#define il inline
#define ri register
#define Size 524288
#define intmax 0x3f3f3f3f
using namespace std;
il void Max(int&,int);
struct segmentree{
	struct data{
		int l,r,d;
	}t[Size];int n1,con;
	il void build(int n,int c){
		for(n1=1;n1<=n;n1<<=1);
		for(int i(1);i<n1<<1;++i)
			t[i].d=-intmax;con=c;
	}il void change(int p,int v){
		t[p+=n1].d=v;
		while(p>>=1)
			t[p].d=max(t[p<<1].d,t[p<<1|1].d);
	}
	il int ask(int l,int r){
		int ans(con);if(l>r)return ans;
		for(l+=n1-1,r+=n1+1;l^r^1;l>>=1,r>>=1){
			if(~l&1)Max(ans,t[l^1].d);
			if(r&1)Max(ans,t[r^1].d);
		}return ans;
	}
}dp1[2];
int dp[Size][2],a[Size],n,
	a1[Size],a2[Size],a3[Size];
il void read(int&);
il bool deal(int,int,int,int,int);
int main(){
	//freopen("in","r",stdin);
	//freopen("out","w",stdout);
	read(n);
	for(int i(1);i<=n;++i)
		read(a[i]),a1[i]=max(a1[i-1],a[i]),
			a2[i]=a1[i]^a[i]?1:2;
	for(int i(n);i;--i)a3[i]=a3[i+1]+(a2[i]^2?0:1);
	dp1[0].build(n,0),dp1[1].build(n,-intmax);
	for(int i(n),j;i;--i)
		for(j=0;j<2;++j)
			dp[i][j]=dp1[j^a2[i]&1].ask(a[i]+1,n)+a2[i],
				dp1[j].change(a[i],dp[i][j]);
	if(!deal(0,0,1,0,0))return puts("-1"),0;
	for(int i(1),j,i1(0),i2(0),a(0),b(0);i<=n;++i){
		for(j=0;j<2;++j)dp1[j].change(::a[i],-intmax);
		deal(i2,max(i1,::a[i]),i+1,a+(i1<::a[i]),b)?
			(a+=i1<::a[i],Max(i1,::a[i]),putchar(48)):
			(b+=i2<::a[i],Max(i2,::a[i]),putchar(49));
	}return 0;
}
il bool deal(int v1,int v2,int p,int a,int b){
	int b1(a-b+a3[p]),b2(b-a+a3[p]);
	return b1>=0&&b1<=dp1[b1&1].ask(v1+1,n)
		||b2>=0&&b2<=dp1[b2&1].ask(v2+1,n);
}
il void read(int&x){
	x^=x;ri char c;while(c=getchar(),c<'0'||c>'9');
	while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
}
il void Max(int&x,int y){
	x=x>y?x:y;
}