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 fi first
#define se second
#define pb push_back
#define SZ(x) ((int)x.size())
#define L(i,u) for (register int i=head[u]; i; i=nxt[i])
#define rep(i,a,b) for (register int i=(a); i<=(b); i++)
#define per(i,a,b) for (register int i=(a); i>=(b); i--)
using namespace std;
typedef long long ll;
typedef unsigned int ui;
typedef pair<int,int> Pii;
typedef vector<int> Vi;
inline void read(int &x) {
	x=0; char c=getchar(); int f=1;
	while (!isdigit(c)) {if (c=='-') f=-1; c=getchar();}
	while (isdigit(c)) {x=x*10+c-'0'; c=getchar();} x*=f;
}
inline ui R() {
	static ui seed=416;
	return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;
}
const int N = 233333, inf = 0x3f3f3f3f;
int n,p[N],cnt0,cnt1,max0,max1,q;bool high[N];
int t,v[2][N];vector<pair<int*,int> >rec[N];//int*
inline int query(int *v, int p){
	int res=-inf;while(p<=n)res=max(res,v[p]),p+=p&-p;return res;//WA
}
inline void modify(int *v, int p, int x){
	while(p){
		if(x>v[p]){rec[t].pb(pair<int*,int>(v+p,v[p]));v[p]=x;}
		p-=p&-p;
	}
}
inline bool judge(int lim, int x){
	if(x<0)return 0;return query(v[x&1],lim+1)>=x;
}
inline bool ok(int max0, int max1, int cnt0, int cnt1){
	return judge(max1,cnt0-cnt1+q)|judge(max0,cnt1-cnt0+q);
}
int main() {
	read(n);for(int i=1,mx=0;i<=n;i++){
		read(p[i]);high[i]=p[i]>mx;mx=max(mx,p[i]);q+=high[i];
	}
	rep(i,0,1)rep(j,0,n)v[i][j]=-inf;modify(v[0],n,0);//WA
	per(i,n,1){
		int f[2];t=i;
		f[0]=query(v[0^(!high[i])],p[i])+(high[i]?2:1);
		f[1]=query(v[1^(!high[i])],p[i])+(high[i]?2:1);
		//printf("%d:%d %d\n",i,f[0],f[1]);
		if(f[0]>=0)modify(v[0],p[i],f[0]);if(f[1]>=0)modify(v[1],p[i],f[1]);
	}
	if(!ok(0,0,0,0)){puts("-1");return 0;}
	rep(i,1,n){
		q-=high[i];rep(j,0,SZ(rec[i])-1)*rec[i][j].fi=rec[i][j].se;
		if(ok(max(max0,p[i]),max1,cnt0+(p[i]>max0),cnt1)){
			putchar('0');cnt0=cnt0+(p[i]>max0);max0=max(max0,p[i]);
		}
		else {
			putchar('1');cnt1=cnt1+(p[i]>max1);max1=max(max1,p[i]);
		}
	}
	return 0;
}