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>
using namespace std;
typedef long long ll;
const int N=200005,p=1000000007;
int read(){
	int f=1,g=0;char ch=getchar();
	for (;!isdigit(ch);ch=getchar()) if (ch=='-') f=-1;
	for (;isdigit(ch);ch=getchar()) g=g*10+ch-'0';
	return f*g;
}
int n,a[N],ma[N],s,g[N][2],ans[N];
void chkmax(int &x,int y){if(x<y) x=y;}
struct segment_tree{
	int f[N<<2][2];
	void build(int x,int l,int r){
		f[x][0]=0;f[x][1]=-1e9;
		if (l==r) return;
		int mid=(l+r)>>1;
		build(x*2,l,mid);
		build(x*2+1,mid+1,r);
	}
	void modi(int x,int l,int r,int pos,int *val){
		if (l==r){f[x][0]=val[0];f[x][1]=val[1];return;}
		int mid=(l+r)>>1;
		if (pos<=mid) modi(x*2,l,mid,pos,val);
		else modi(x*2+1,mid+1,r,pos,val);
		f[x][0]=max(f[x*2][0],f[x*2+1][0]);
		f[x][1]=max(f[x*2][1],f[x*2+1][1]);
	}
	void que(int x,int l,int r,int pos,int *t){
		if (l>=pos) {chkmax(t[0],f[x][0]);chkmax(t[1],f[x][1]);return;}
		int mid=(l+r)>>1;
		que(x*2+1,mid+1,r,pos,t);
		if (pos<=mid) que(x*2,l,mid,pos,t);
	}
	void modify(int pos,int *val){modi(1,1,n,pos,val);}
	void query(int pos,int *t){que(1,1,n,pos,t);}
}f;
bool check(int cnt0,int m0,int cnt1,int m1){
	int g[2],v[2]={cnt1-cnt0+s,cnt0-cnt1+s};
	g[0]=0;g[1]=-1e9;f.query(m0,g);
	if ((v[0]>=0)&&(g[v[0]&1]>=v[0])) return 1;
	g[0]=0;g[1]=-1e9;f.query(m1,g);
	if ((v[1]>=0)&&(g[v[1]&1]>=v[1])) return 1;
	return 0;
}
int main(){
	n=read();
	for (int i=1;i<=n;i++) a[i]=read(),ma[i]=max(a[i],ma[i-1]);
	f.build(1,1,n);
	for (int i=n;i;i--){
		g[i][1]=-1e9;
		f.query(a[i],g[i]);s+=(a[i]==ma[i]);
		if (a[i]!=ma[i]) swap(g[i][0],g[i][1]);
		g[i][0]+=1+(a[i]==ma[i]);g[i][1]+=1+(a[i]==ma[i]);
		f.modify(a[i],g[i]);
	}
	g[0][1]=-1e9;
	int cnt0=0,cnt1=0,m0=0,m1=0;
	for (int i=1;i<=n;i++){
		f.modify(a[i],g[0]);s-=(a[i]==ma[i]);
		if (check(cnt0+(a[i]>m0),max(m0,a[i]),cnt1,m1)){cnt0+=(a[i]>m0);m0=max(m0,a[i]);ans[i]=0;}
		else {cnt1+=(a[i]>m1);m1=max(m1,a[i]);ans[i]=1;}
	}
	if (cnt0!=cnt1) puts("-1");
	else{
		for (int i=1;i<=n;i++) putchar(ans[i]+'0');
		puts("");
	}
	return 0;
}