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 <string>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fd(i,a,b) for(int i=a;i>=b;i--)
using namespace std;

int read() {
	char ch;
	for(ch=getchar();ch<'0'||ch>'9';ch=getchar());
	int x=ch-'0';
	for(ch=getchar();ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0';
	return x;
}

const int N=2e5+5,inf=0x7fffffff;

struct Segment_Tree{
	int mx[N<<2];
	void modify(int v,int l,int r,int x,int y) {
		if (l==r) {mx[v]=y;return;}
		int mid=l+r>>1;
		if (x<=mid) modify(v<<1,l,mid,x,y);
		else modify(v<<1|1,mid+1,r,x,y);
		mx[v]=max(mx[v<<1],mx[v<<1|1]);
	}
	int query(int v,int l,int r,int x,int y) {
		if (x>y) return 0;
		if (x<=l&&r<=y) return mx[v];
		int mid=l+r>>1,tmp=-inf;
		if (x<=mid) tmp=max(tmp,query(v<<1,l,mid,x,y));
		if (y>mid) tmp=max(tmp,query(v<<1|1,mid+1,r,x,y));
		return tmp;
	}
}tr[2];

int n,p[N],cnt[N],mx;

bool chk(int x,int mx0,int c0,int mx1,int c1) {
	int v0=c0+cnt[x]-c1,v1=c1+cnt[x]-c0;
	if (v0>=0&&tr[v0&1].query(1,1,n,mx1+1,n)>=v0) return 1;
	if (v1>=0&&tr[v1&1].query(1,1,n,mx0+1,n)>=v1) return 1;
	return 0;
}

void print(string s) {
	int n=s.length();
	fo(i,0,n-1) putchar(s[i]);
}

int main() {
	n=read();
	fo(i,1,n) {
		p[i]=read();
		if (p[i]>mx) mx=p[i],cnt[i]=1;
	}
	fo(i,1,n<<2) tr[1].mx[i]=-inf;
	fd(i,n,1) {
		int f0=tr[0].query(1,1,n,p[i],n);
		int f1=tr[1].query(1,1,n,p[i],n);
		if (cnt[i]) {
			tr[0].modify(1,1,n,p[i],f0+2);
			tr[1].modify(1,1,n,p[i],f1+2);
		} else {
			tr[1].modify(1,1,n,p[i],f0+1);
			tr[0].modify(1,1,n,p[i],f1+1);
		}
	}
	fd(i,n,1) cnt[i]+=cnt[i+1];
	string s="";int mx0=0,mx1=0,c0=0,c1=0;
	fo(i,1,n) {
		tr[0].modify(1,1,n,p[i],0);
		tr[1].modify(1,1,n,p[i],-inf);
		if (chk(i+1,max(mx0,p[i]),c0+(p[i]>mx0),mx1,c1)) {
			c0+=p[i]>mx0;mx0=max(mx0,p[i]);
			s.push_back('0');
		} else {
			c1+=p[i]>mx1;mx1=max(mx1,p[i]);
			s.push_back('1');
		}
	}
	if (c0==c1) print(s);
	else puts("-1");
	return 0;
}