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>
#include<vector>
#define gmx(x,y) x=(x>(y)?x:(y))
#define gmi(x,y) x=(x<(y)?x:(y))
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
using namespace std;
const int N=200200,INF=1000010000;
int n,m,Q,X,Y,cx,cy,mi,t[2],a[N],b[N],c[2][N];
char s[N];
struct ele{
	int k,x,y;
	ele(int _k=0,int _x=0,int _y=0){k=_k,x=_x,y=_y;}
};
vector<ele>q[N];
void cha(int k,int x,int y,int I){
	for(;x<=m;x+=x&-x)
		q[I].push_back(ele(k,x,c[k][x])),gmx(c[k][x],y);
}
int ask(int k,int x){int y=-INF;for(;x;x-=x&-x) gmx(y,c[k][x]);return y;}
bool chk(int X,int C){return C>=0 && ask(C&1,X)>=C;}
int main(){
	//freopen("1.in","r",stdin);
	scanf("%d",&n);m=n+1;
	FOR(i,1,n) scanf("%d",&a[i]),a[i]=m-a[i];
	a[0]=INF;
	FOR(i,1,n)if(a[i]<a[mi]) mi=i,b[i]=1,Q++;
	//FOR(i,1,n) cout<<a[i]<<' ';cout<<'\n';
	//FOR(i,1,n) cout<<b[i]<<' ';cout<<'\n';
	FOR(i,1,n) c[1][i]=-INF;
	ROF(i,n,1){
		FOR(k,0,1) t[k]=ask(k,a[i]);
		//cout<<t[0]<<' '<<t[1]<<'\n';
		FOR(k,0,1) cha(k^b[i]^1,a[i],t[k]+b[i]+1,i);
	}
	if(ask(Q&1,n)<Q) return puts("-1"),0;
	X=Y=n+1;
	FOR(i,1,n){
		for(ele e:q[i]) c[e.k][e.x]=e.y;Q-=b[i];
		int tX=X,tC=cx;
		cx+=a[i]<X;gmi(X,a[i]);s[i]='0';
		//cout<<X<<' '<<cx<<' '<<Y<<' '<<cy<<' '<<Q<<'\n';
		if(!chk(X,cy+Q-cx) && !chk(Y,cx+Q-cy))
			s[i]='1',X=tX,cx=tC,cy+=a[i]<Y,gmi(Y,a[i]);
	}
	puts(s+1);
}