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 <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <queue>
#include <functional>
#include <cmath>
#include <set>
#include <map>
#include <string>
#include <cassert>
#define SIZE 200005
#define BT 1024*128*2*2

using namespace std;
typedef long long int ll;
typedef pair <int,int> P;

struct segtree//max 取るやつ、常に0以上じゃなきゃだめ、まだverifyしてない
{
	P seg[BT];
	int mum;
	
	void init(int n)
	{
		mum=1;
		while(mum<n) mum<<=1;
		for(int i=0;i<mum*2;i++) seg[i]=P(-1,-1);
	}
	void add(int k,P x)
	{
		k+=mum-1;
		seg[k]=x;
		while(k>0)
		{
			k=(k-1)/2;
			seg[k]=max(seg[k*2+1],seg[k*2+2]);
		}
	}
	P get(int a,int b,int k,int l,int r)
	{
		if(b<=l||r<=a) return P(-1,-1);
		if(a<=l&&r<=b) return seg[k];
		else
		{
			P vl=get(a,b,k*2+1,l,(l+r)/2);
			P vr=get(a,b,k*2+2,(l+r)/2,r);
			return max(vl,vr);
		}
	}
	P get(int a,int b)
	{
		return get(a,b,0,0,mum);
	}
};
segtree odd,even;
int A[SIZE];
bool high[SIZE];
bool yy[SIZE];
int to[SIZE],te[SIZE];
int d0[SIZE],d1[SIZE];
int n,r;

string solve1()//X: high only
{
	odd.init(n+2);
	even.init(n+2);
	even.add(n,P(0,-1));
	int pos=-1;
	for(int i=n-1;i>=0;i--)
	{
		P vl=odd.get(A[i],n+1);
		P vr=even.get(A[i],n+1);
		if(vl.first!=-1)
		{
			to[i]=vl.second;
			int len=vl.first;
			if(high[i]) len+=2;
			else len++;
			if(len<r)
			{
				if(len%2==0) even.add(A[i],P(len,i));
				else odd.add(A[i],P(len,i));
			}
			else if(len==r)
			{
				pos=i;
				break;
			}
		}
		vl=vr;
		if(vl.first!=-1)
		{
			te[i]=vl.second;
			int len=vl.first;
			if(high[i]) len+=2;
			else len++;
			if(len<r)
			{
				if(len%2==0) even.add(A[i],P(len,i));
				else odd.add(A[i],P(len,i));
			}
			else if(len==r)
			{
				pos=i;
				break;
			}
		}
	}
	if(pos==-1) return "";
	int now=r;
	memset(yy,false,sizeof(yy));
	while(pos!=-1)
	{
		yy[pos]=true;
		if(high[pos]) now-=2;
		else now--;
		if(now%2==0) pos=te[pos];
		else pos=to[pos];
	}
	string ans="";
	int mx=-1;
	for(int i=0;i<n;i++)
	{
		if(yy[i]) ans+="1";
		else
		{
			if(high[i]||mx>A[i])
			{
				mx=max(mx,A[i]);
				ans+="0";
			}
			else ans+="1";
		}
	}
	return ans;
}
string solve2()//Y: high only
{
	odd.init(n+2);
	even.init(n+2);
	even.add(n,P(0,-1));
	int pos=-1;
	for(int i=n-1;i>=0;i--)
	{
		d0[i]=d1[i]=-1;
		P vl=odd.get(A[i],n+1);
		P vr=even.get(A[i],n+1);
		if(vl.first!=-1)
		{
			to[i]=vl.second;
			int len=vl.first;
			if(high[i]) len+=2;
			else len++;
			if(len%2==0) even.add(A[i],P(len,i));
			else odd.add(A[i],P(len,i));
			if(len%2==1) d1[i]=len;
			else d0[i]=len;
		}
		vl=vr;
		if(vl.first!=-1)
		{
			te[i]=vl.second;
			int len=vl.first;
			if(high[i]) len+=2;
			else len++;
			if(len%2==0) even.add(A[i],P(len,i));
			else odd.add(A[i],P(len,i));
			if(len%2==1) d1[i]=len;
			else d0[i]=len;
		}
	}
	int zan=r;
	string ans="";
	int mx=-1;
	for(int i=0;i<n;i++)
	{
		if(mx>A[i]) ans+="0";
		else
		{
			if(zan==0) ans+="1";
			else
			{
				if((zan%2==1&&d1[i]>=zan)||(zan%2==0&&d0[i]>=zan))
				{
					mx=A[i];
					if(high[i]) zan-=2;
					else zan--;
					ans+="0";
				}
				else ans+="1";
			}
		}
	}
	if(zan!=0) return "";
	return ans;
}
int main()
{
	n;
	scanf("%d",&n);
	for(int i=0;i<n;i++)
	{
		scanf("%d",&A[i]);
		A[i]--;
	}
	int mx=-1;
	r=0;
	for(int i=0;i<n;i++)
	{
		if(mx<A[i])
		{
			r++;
			mx=A[i];
			high[i]=true;
		}
		else high[i]=false;
	}
	//for(int i=0;i<n;i++) printf("%d",high[i]);puts("");
	if(n%2==1&&r==n)
	{
		puts("-1");
		return 0;
	}
	string a1=solve1();
	string a2=solve2();
	//printf("%s %s\n",a1.c_str(),a2.c_str());
	if(a1=="") a1=a2;
	else if(a2!="") a1=min(a1,a2);
	if(a1=="") puts("-1");
	else printf("%s\n",a1.c_str());
	//printf("%s\n",a2.c_str());
	return 0;
}