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;
int gi() {
	char ch='!'; int res=0, f=0;
	while(ch<'0' || ch>'9') { ch=getchar(); if(ch == '-') f=1; }
	while(ch>='0' && ch<='9') res=res*10+ch-'0', ch=getchar();
	return f?-res:res;
}
const int N=2e5+100;
int n,p[N],val[N],cntx,cnty,Hx,Hy,tot;
char str[N];
struct segment_tree {
#define ls (k<<1)
#define rs (k<<1|1)
	int mx[N<<2];
	segment_tree() { memset(mx,0xcf,sizeof(mx)); }
	void mdf(int k,int tar,int val,int l=1,int r=n) {
		if(l == r) { mx[k]=val; return; }
		int mid=(l+r)>>1;
		tar <= mid ? mdf(ls,tar,val,l,mid):mdf(rs,tar,val,mid+1,r);
		mx[k]=max(mx[ls],mx[rs]);
	}
	int qry(int k,int ql,int qr,int l=1,int r=n) {
		if(ql <= l && r <= qr) return mx[k];
		int mid=(l+r)>>1,res=mx[0];
		if(ql <= mid) res=max(res,qry(ls,ql,qr,l,mid));
		if(qr > mid) res=max(res,qry(rs,ql,qr,mid+1,r));
		return res;
	}
} s[2];
bool check(int val,int t) {
	if(val<0) return 0;
	if(t == n) return val == 0;
	return s[val&1].qry(1,t+1,n)>=val;
}
int main() {
	n=gi();
	for(int i=1,mx=0;i<=n;++i) {
		p[i]=gi();
		if(p[i]>mx) mx=p[i], val[i]=2, ++tot;
		else val[i]=1;
	}
	for(int i=n;i>=1;--i) {
		int mx0=max(s[0].qry(1,p[i],n),0), mx1=s[1].qry(1,p[i],n);
		if(val[i] == 1)
			s[0].mdf(1,p[i],mx1+1), s[1].mdf(1,p[i],mx0+1);
		else
			s[0].mdf(1,p[i],mx0+2), s[1].mdf(1,p[i],mx1+2);
	}
	for(int i=1,mx=0;i<=n;++i) {
		s[0].mdf(1,p[i],s[0].mx[0]), s[1].mdf(1,p[i],s[1].mx[0]);
		if(p[i]>mx) mx=p[i], --tot;
		//try:0
		if(check(cntx-cnty+tot+(p[i]>Hx),Hy) || check(cnty-cntx+tot-(p[i]>Hx),Hx))
			str[i]='0', cntx += (p[i]>Hx), Hx=max(Hx,p[i]);
		//try:1
		else str[i]='1', cnty += (p[i]>Hy), Hy=max(Hy,p[i]);
	}
	if(cntx != cnty) puts("-1");
	else puts(str+1);
	return 0;
}