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<algorithm>
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
typedef long long LL;
typedef pair<int,int> PI;
const int N=200005;
int a[N];
int n;
bool ok[N];
int id;
struct qq
{
	int f[N];
	vector<PI> vec[N];
	int lb (int x)	{return x&(-x);}
	void modify (int x,int c)
	{
		while (x<=n)
		{
			if (f[x]<c)	{vec[id].push_back({x,f[x]});f[x]=c;}
			x+=lb(x);
		}
	}
	int query (int x)
	{
		int lalal=0;
		while (x>=1)	{lalal=max(lalal,f[x]);x-=lb(x);}
		return lalal;
	}
	void upd ()
	{
		int siz=vec[id].size();
		for (int u=0;u<siz;u++) f[vec[id][u].first]=vec[id][u].second;
	}
}A,B,C;
//A:奇数     B:偶数 
void Init ()
{
	int mn=n+1;for (int u=1;u<=n;u++)	{ok[u]=(a[u]<mn);mn=min(mn,a[u]);}
	for (int u=n;u>=1;u--)
	{
		id=u;int t,t1;
		if (ok[u])//这是一个特殊点 
		{
			t=A.query(a[u]);if (t&1) A.modify(a[u],t+2);
			t=B.query(a[u]);B.modify(a[u],t+2);
		}
		else
		{
			t=A.query(a[u]),t1=B.query(a[u]);
			A.modify(a[u],t1+1);
			if (t&1) B.modify(a[u],t+1);
			
			t=C.query(a[u]);C.modify(a[u],t+1);
		}
	}
}
int lena,lenb,Q;
int Mn;
int h[2];
bool check ()
{
	bool tf=false;
	int x=lena-lenb+Q;
	if (x>=0)
	{
		if (x&1) tf|=(A.query(h[1])>=x);
		else tf|=(B.query(h[1])>=x);
	}
	x=lenb-lena+Q;
	if (x>=0)
	{
		if (x&1) tf|=(A.query(h[0])>=x);
		else tf|=(B.query(h[0])>=x);
	}
	return tf;
}
int main()
{
	scanf("%d",&n);
	for (int u=1;u<=n;u++) scanf("%d",&a[u]);
	for (int u=1;u<=n;u++) a[u]=n-a[u]+1;
	Init();
	h[0]=h[1]=n;
	for (int u=1;u<=n;u++) Q=Q+ok[u];
	if (!check())	{printf("-1\n");return 0;}
	for (int u=1;u<=n;u++)
	{
	//	printf("YES:%d\n",u);
		id=u;A.upd();B.upd();C.upd();
		Q=Q-ok[u];
		//这一位填0
		lena=lena+(h[0]>=a[u]);
		if (check())	{h[0]=min(h[0],a[u]);printf("0");continue;}
		lena=lena-(h[0]>=a[u]);
		lenb=lenb+(h[1]>=a[u]);
		h[1]=min(h[1],a[u]);
		printf("1");
	}
	return 0;
}