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:
//by yjz
#include<bits/stdc++.h>
using namespace std;
#define FF first
#define SS second
#define PB push_back
#define MP make_pair
#define foreach(it,s) for(__typeof((s).begin()) it=(s).begin();it!=(s).end();it++)
#ifndef LOCAL
#define cerr if(0)cout
#endif
typedef long long ll;
const int mod=1e9+7;
//My i/o stream
struct fastio
{
	char s[100000];
	int it, len;
	fastio() {it=len=0;}
	inline char get()
	{
		if (it<len) return s[it++]; it=0;
		len=fread(s, 1, 100000, stdin);
		if (len==0) return EOF; else return s[it++];
	}
	bool notend()
	{
		char c=get();
		while (c==' '||c=='\n') c=get();
		if (it>0) it--;
		return c!=EOF;
	}
}_buff;
#define geti(x) x=getnum()
#define getii(x,y) geti(x),geti(y)
#define getiii(x,y,z) getii(x,y),geti(z)
#define puti(x) putnum(x),putchar(' ')
#define putii(x,y) puti(x),puti(y)
#define putiii(x,y,z) putii(x,y),puti(z)
#define putsi(x) putnum(x),putchar('\n')
#define putsii(x,y) puti(x),putsi(y)
#define putsiii(x,y,z) putii(x,y),putsi(z)
inline ll getnum()
{
	ll r=0; bool ng=0; char c; c=_buff.get();
	while (c!='-'&&(c<'0'||c>'9')) c=_buff.get();
	if (c=='-') ng=1, c=_buff.get();
	while (c>='0'&&c<='9') r=r*10+c-'0', c=_buff.get();
	return ng?-r:r;
}
template <class T> inline void putnum(T x)
{
	if (x<0) putchar('-'), x=-x;
	register short a[20]={}, sz=0;
	while (x) a[sz++]=x%10, x/=10;
	if(sz==0) putchar('0');
	for (int i=sz-1; i>=0; i--) putchar('0'+a[i]);
}
inline char getreal() {char c=_buff.get(); while (c<=32) c=_buff.get(); return c;}
ll qpow(ll x, ll k) {return k==0? 1: 1ll*qpow(1ll*x*x%mod,k>>1)*(k&1?x:1)%mod;}
const int maxn = 200111;
const ll B = 1000000;
struct SGT
{
	struct node
	{
		int mx[2];
		int tl, tr;
		node(){mx[0]=0; mx[1]=-1000000001;}
	}a[maxn*100];
	#define ls a[p].tl
	#define rs a[p].tr
	int tot;
	int newnode(int q)
	{
		int p = ++tot;
		assert(p<maxn*100);
		ls = a[q].tl;
		rs = a[q].tr;
		a[p].mx[0] = a[q].mx[0];
		a[p].mx[1] = a[q].mx[1];
		return p;
	}
	void update(int p)
	{
		a[p].mx[0] = max(a[ls].mx[0], a[rs].mx[0]);
		a[p].mx[1] = max(a[ls].mx[1], a[rs].mx[1]);
	}
	int modify(int x, ll v, int l, int r, int q)
	{
		int p = newnode(q);
		if (l==r)
		{
			a[p].mx[v&1] = v;
			return p;
		}
		int m = l+r>>1;
		if (x<=m) ls = modify(x, v, l, m, a[q].tl);
		else rs = modify(x, v, m+1, r, a[q].tr);
		update(p);
		return p;
	}
	int query(int x, int y, int v, int l, int r, int p)
	{
		if (x<=l&&r<=y) return a[p].mx[v];
		if (r<x||y<l) return (v==0?0:-1000000001);
		int m = l+r>>1;
		return max(query(x, y, v, l, m, ls), query(x, y, v, m+1, r, rs));
	}
}sgt;
int n;
int a[maxn], sc[maxn], ver[maxn];
bool top[maxn];
ll dp[maxn][2];
int suf_sum[maxn], mx_ntop[maxn];
char ans[maxn];
bool check(int na, int nb, int ca, int cb, int l)
{
	bool ret = 0;
	int base = suf_sum[l+1];
	int t = nb-na+base;
	if (t>=0)
	{
		int tmp = t%2;
		ll ans = sgt.query(ca+1, n, tmp, 1, n, ver[l+1]);
		ret |= ans>=t;
	}
	swap(na, nb);
	swap(ca, cb);
	t = nb-na+base;
	if (t>=0)
	{
		int tmp = t%2;
		ll ans = sgt.query(ca+1, n, tmp, 1, n, ver[l+1]);
		ret |= ans>=t;
	}
	return ret;
}
void prework()
{
	ver[n+1] = 0;
	int lst = 0;
	for (int i=n; i>=1; i--)
	{
		int tmp = sc[i]&1;
		dp[i][0] = sgt.query(a[i]+1, n, tmp, 1, n, lst)+sc[i];
		dp[i][1] = sgt.query(a[i]+1, n, tmp^1, 1, n, lst)+sc[i];
		lst = sgt.modify(a[i], dp[i][0], 1, n, lst);
		lst = sgt.modify(a[i], dp[i][1], 1, n, lst);
		ver[i] = lst;
//		cerr<<dp[i][0]<<","<<dp[i][1]<<endl;
	}
}
int main()
{
	geti(n);
	int mx = 0;
	for (int i=1; i<=n; i++)
	{
		geti(a[i]);
		if (a[i]>mx)
		{
			mx = a[i];
			top[i] = 1;
			sc[i] = 2;
		}
		else sc[i] = 1;
	}
	for (int i=n; i>=1; i--)
	{
		suf_sum[i] = suf_sum[i+1]+top[i];
		mx_ntop[i] = mx_ntop[i+1];
		if (!top[i])
		{
			mx_ntop[i] = max(mx_ntop[i], a[i]);
		}
	}
	prework();
	
	int na = 0, nb = 0;
	int ca = 0, cb = 0;
	if (!check(na, nb, ca, cb, 0))
	{
		puts("-1");
		return 0;
	}
	for (int i=1; i<=n; i++)
	{
		if (check(na+(a[i]>ca), nb, max(ca, a[i]), cb, i))
		{
			na += a[i]>ca;
			ca = max(ca, a[i]);
			ans[i] = '0';
		}
		else// if (check(na, nb+(a[i]>cb), ca, max(cb, a[i]), i))
		{
			nb += a[i]>cb;
			cb = max(cb, a[i]);
			ans[i] = '1';
		}
/*		else
		{
			puts("-1");
			return 0;
		}
		*/
	}
	printf("%s\n", ans+1);
	return 0;
}