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 a[200001],n,m,v[200001],cnf[200001],cx,cy,mx,my;
char s[200001];
struct yu
{
	int f[600001];
	void make(int x,int l,int r)
	{
		if (l==r){f[x]=-19260817;return;}
		make(x*2,l,l+r>>1),make(x*2+1,(l+r>>1)+1,r);
		f[x]=max(f[x*2],f[x*2+1]);
	}
	void chan(int x,int l,int r,int z,int o)
	{
		if (l==r){f[x]=o;return;}
		if ((l+r>>1)>=z)chan(x*2,l,l+r>>1,z,o);else chan(x*2+1,(l+r>>1)+1,r,z,o);
		f[x]=max(f[x*2],f[x*2+1]);
	}
	int find(int x,int l,int r,int st,int en)
	{
		if (l==st&&r==en)return f[x];
		int mid=l+r>>1;
		if (mid>=en)return find(x*2,l,mid,st,en);else
		if (mid<st)return find(x*2+1,mid+1,r,st,en);else
		return max(find(x*2,l,mid,st,mid),find(x*2+1,mid+1,r,mid+1,en));
	}
}od,ev;
bool che(int x,int q)
{
	if (q<0)return false;
	if (q%2==1)return od.find(1,1,n,max(x,1),n)>=q;else return ev.find(1,1,n,(max(x,1)),n)>=q;
}
int main()
{
	scanf("%d",&n);
	for (int i=1;i<=n;i++)scanf("%d",&a[i]),v[i]=(a[i]>m?2:1),m=max(m,a[i]);
	od.make(1,1,n);
	for (int i=n;i;i--)
	{
		mx=od.find(1,1,n,a[i],n),my=ev.find(1,1,n,a[i],n);
		if (v[i]==1)od.chan(1,1,n,a[i],my+v[i]),ev.chan(1,1,n,a[i],mx+v[i]);else
		od.chan(1,1,n,a[i],mx+v[i]),ev.chan(1,1,n,a[i],my+v[i]);
	}
	for (int i=n;i;i--)cnf[i]=cnf[i+1]+v[i]-1;mx=my=0;
	for (int i=1;i<=n;i++)
	{
		od.chan(1,1,n,a[i],-19260817);ev.chan(1,1,n,a[i],0);
		if (che(my,cx+cnf[i+1]-cy+(a[i]>mx)))s[i]='0',cx+=a[i]>mx,mx=max(mx,a[i]);else
		if (che(max(mx,a[i]),cy+cnf[i+1]-cx-(a[i]>mx)))s[i]='0',cx+=a[i]>mx,mx=max(mx,a[i]);else
		s[i]='1',cy+=a[i]>my,my=max(my,a[i]);
	}
	if (cy!=cx)printf("-1\n");else printf("%s\n",s+1);
}