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 for1(a,b,i) for(int i=a;i<=b;++i)
#define FOR2(a,b,i) for(int i=a;i>=b;--i)
using namespace std;
typedef long long ll;
inline int read() {
	int f=1,sum=0;
	char x=getchar();
	for(;(x<'0'||x>'9');x=getchar()) if(x=='-') f=-1;
	for(;x>='0'&&x<='9';x=getchar()) sum=sum*10+x-'0';
	return f*sum;
}

#define M 1000005
int n;
int vis[M];
int a[M],f[M][2],Max[M*4][2];

inline pair<int,int> query(int g,int l,int r,int lx,int rx) {
	if(lx>rx) return make_pair(0,0);
	if(lx<=l&&rx>=r) return make_pair(Max[g][0],Max[g][1]);
	pair<int,int> ans=make_pair(0,0);
	int mid=l+r>>1;
	if(lx<=mid) ans=query(g<<1,l,mid,lx,rx);
	if(rx>mid) {
		pair<int,int> y=query(g<<1|1,mid+1,r,lx,rx);
		ans.first=max(ans.first,y.first);
		ans.second=max(ans.second,y.second);
	}
	return ans;
}

inline void T_add(int g,int l,int r,int x,int id) {
	if(l==r) return Max[g][0]=f[id][0],Max[g][1]=f[id][1],void();
	int mid=l+r>>1;
	if(x<=mid) T_add(g<<1,l,mid,x,id);
	else       T_add(g<<1|1,mid+1,r,x,id);
	Max[g][0]=max(Max[g<<1][0],Max[g<<1|1][0]);
	Max[g][1]=max(Max[g<<1][1],Max[g<<1|1][1]);
}

inline bool check(int val,int to) {
	if(to<0) return 0;
	pair<int,int> y=query(1,1,n,val+1,n);
	if(!(y.first-to&1)) return y.first>=to;
	else return y.second>=to;
}

int main () {
	//freopen("a.in","r",stdin);
	n=read();
	for1(1,n,i) a[i]=read();
	
	for(int x=0,i=1;i<=n;++i) {
		x=max(x,a[i]);
		if(x==a[i]) ++vis[i];
	}
	FOR2(n,1,i) vis[i]+=vis[i+1];
	
	FOR2(n,1,i) {
		int t=1+(vis[i]!=vis[i+1]);
		pair<int,int> y=query(1,1,n,a[i]+1,n);
		f[i][y.first+t&1]=max(f[i][y.first+t&1],y.first+t);
		f[i][y.second+t&1]=max(f[i][y.second+t&1],y.second+t);
		T_add(1,1,n,a[i],i);
	}
	
	if(!check(0,vis[1])) return puts("-1"),0;
	
	for(int i=1,len[2]={0},pos[2]={0};i<=n;++i) {
		f[i][0]=f[i][1]=0;
		T_add(1,1,n,a[i],i);
		int x=a[i]>a[pos[0]]?i:pos[0],y=len[0]+(x==i);
		if(check(a[x],len[1]+vis[i+1]-y)||check(a[pos[1]],y+vis[i+1]-len[1])) {
			pos[0]=x,len[0]=y,putchar('0');
		}
		else {
			pos[1]=a[i]>a[pos[1]]?i:pos[1];
			len[1]+=pos[1]==i;
			putchar('1');
		}
	}
	puts("");
}