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 p[200010],Q[200010],v[200010],Cx,Cy,Hx,Hy,n,ma;
bool bo;

struct node
{
	int ls[4000010],rs[4000010],val[4000010],rt[200010],tot;
	void add(int i,int I,int l,int r,int x,int v)
	{
		val[i]=max(val[I],v);
		if (l==r) return;
		int mid=(l+r)>>1;
		if (x<=mid) rs[i]=rs[I],add(ls[i]=(++tot),ls[I],l,mid,x,v);
		else ls[i]=ls[I],add(rs[i]=(++tot),rs[I],mid+1,r,x,v);
	}
	int query(int i,int l,int r,int ql,int qr)
	{
		if (ql>qr) return val[0];
		if (l==ql&&r==qr) return val[i]==0?val[0]:val[i];
		int mid=(l+r)>>1;
		if (qr<=mid) return ls[i]?query(ls[i],l,mid,ql,qr):val[0];
		if (ql>mid) return rs[i]?query(rs[i],mid+1,r,ql,qr):val[0];
		return max(ls[i]?query(ls[i],l,mid,ql,mid):val[0],rs[i]?query(rs[i],mid+1,r,mid+1,qr):val[0]);
	}
}t[2];

int main()
{
	scanf("%d",&n),ma=0;
	for (int i=1; i<=n; i++) 
	{
		scanf("%d",&p[i]);
		if (p[i]>ma) v[i]=2,ma=p[i]; else v[i]=1;
	}
	Q[n+1]=0;
	for (int i=n; i; i--) Q[i]=Q[i+1]+v[i]-1;
	t[0].rt[n+1]=t[1].rt[n+1]=t[0].tot=t[1].tot=1,t[1].val[0]=-2*n-1;
	for (int i=n; i; i--)
		if (v[i]==2)
		{
			t[0].add(t[0].rt[i]=(++t[0].tot),t[0].rt[i+1],1,n,p[i],2+t[0].query(t[0].rt[i+1],1,n,p[i]+1,n));
			t[1].add(t[1].rt[i]=(++t[1].tot),t[1].rt[i+1],1,n,p[i],2+t[1].query(t[1].rt[i+1],1,n,p[i]+1,n));
		} else
		{
			t[0].add(t[0].rt[i]=(++t[0].tot),t[0].rt[i+1],1,n,p[i],1+t[1].query(t[1].rt[i+1],1,n,p[i]+1,n));
			t[1].add(t[1].rt[i]=(++t[1].tot),t[1].rt[i+1],1,n,p[i],1+t[0].query(t[0].rt[i+1],1,n,p[i]+1,n));
		}
	Cx=Cy=Hx=Hy=0,bo=0;
	int nw=Cy-Cx+Q[1];
	if (nw>=0&&t[nw&1].query(t[nw&1].rt[1],1,n,Hx+1,n)>=nw) bo=1;
	nw=Cx-Cy+Q[1];
	if (nw>=0&&t[nw&1].query(t[nw&1].rt[1],1,n,Hy+1,n)>=nw) bo=1;
	if (!bo) return puts("-1"),0;
	for (int i=1; i<=n; i++)
	{
		int cx=Cx+(p[i]>Hx),hx=max(Hx,p[i]),cy=Cy,hy=Hy,nw;
		nw=cy-cx+Q[i+1];
		if (nw>=0&&t[nw&1].query(t[nw&1].rt[i+1],1,n,hx+1,n)>=nw) 
		{
			putchar('0'),Hx=hx,Hy=hy,Cx=cx,Cy=cy;
			continue;
		}
		nw=cx-cy+Q[i+1];
		if (nw>=0&&t[nw&1].query(t[nw&1].rt[i+1],1,n,hy+1,n)>=nw) 
		{
			putchar('0'),Hx=hx,Hy=hy,Cx=cx,Cy=cy;
			continue;
		}
		Cy+=(p[i]>Hy),Hy=max(Hy,p[i]),putchar('1');
	}
	return puts(""),0;
}