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:
// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
	int X=0,w=1; char c=getchar();
	while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
	while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
	return X*w;
}

const int N=200000+10;
const int inf=0x3f3f3f40;

int n,a[N],w[N],cnt[N]; char s[N];

#define ls (o<<1)
#define rs (o<<1|1)
struct sgt {
	int maxv[N<<2];
	void pushup(int o) { maxv[o]=max(maxv[ls],maxv[rs]); }
	void modify(int o,int l,int r,int p,int w) {
		if (l==r) { maxv[o]=w; return; }
		int mid=(l+r)>>1;
		if (p<=mid) modify(ls,l,mid,p,w);
		else modify(rs,mid+1,r,p,w);
		pushup(o);
	}
	int query(int o,int l,int r,int ql,int qr) {
		if (ql<=l&&r<=qr) return maxv[o];
		int mid=(l+r)>>1,res=-inf;
		if (ql<=mid) res=max(res,query(ls,l,mid,ql,qr));
		if (qr>mid) res=max(res,query(rs,mid+1,r,ql,qr));
		return res;
	}
} odd,even;
#undef ls
#undef rs

bool check(int p,int w) {
	if (w<0) return 0;
	if (w&1) return odd.query(1,1,n,p,n)>=w;
	else return even.query(1,1,n,p,n)>=w;
}

int main() {
	n=read();
	for (int i=1;i<=n;++i) a[i]=read();
	for (int i=1,mx=0;i<=n;++i) {
		if (a[i]>mx) w[i]=2,mx=a[i];
		else w[i]=1;
	}
	memset(odd.maxv,0xc0,sizeof(odd.maxv));
	for (int i=n;i;--i) {
		int mxo=odd.query(1,1,n,a[i],n),mxe=even.query(1,1,n,a[i],n);
		if (w[i]&1) odd.modify(1,1,n,a[i],mxe+w[i]),even.modify(1,1,n,a[i],mxo+w[i]);
		else odd.modify(1,1,n,a[i],mxo+w[i]),even.modify(1,1,n,a[i],mxe+w[i]);
	}
	for (int i=n;i;--i) cnt[i]=cnt[i+1]+w[i]-1;
	int cx=0,cy=0,mxx=0,mxy=0;
	for (int i=1;i<=n;++i) {
		odd.modify(1,1,n,a[i],-inf),even.modify(1,1,n,a[i],0);
		if (check(mxy,cx+(a[i]>mxx)+cnt[i+1]-cy)
		  ||check(max(mxx,a[i]),cy+cnt[i+1]-cx-(a[i]>mxx)))
			s[i]='0',cx+=(a[i]>mxx),mxx=max(mxx,a[i]);
		else s[i]='1',cy+=(a[i]>mxy),mxy=max(mxy,a[i]);
	}
	if (cx!=cy) puts("-1");
	else for (int i=1;i<=n;++i) putchar(s[i]);
	return 0;
}
// 爬~