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>
#define ci const int&
#define pi pair<int,int>
#define f first
#define s second
using namespace std;
int n,p[200010],tg[200010],mx,t1,t2,n1,n2,l1,l2,tt,nm1,nm2,tmp;
struct BIT{
	int val[200010],tim;
	vector<pi>chg[200010];
	void Ins(int x,ci v){
		x=n-x+1;
		while(x<=n)val[x]<v?chg[tim].push_back((pi){x,val[x]}),val[x]=v:0,x+=(x&-x);
	}
	void Back(){
		for(int i=(int)chg[tim].size()-1;i>=0;--i)val[chg[tim][i].f]=chg[tim][i].s,chg[tim].pop_back();
		--tim;
	}
	int Que(int x){
		x=n-x+1;
		int ret=-1e9;
		while(x)ret=max(ret,val[x]),x-=(x&-x);
		return ret;
	}
}od,ev;
bool Check(){
	tmp=n1+tt-n2;
	if(tmp>=0&&(((tmp&1)&&od.Que(nm2)>=tmp)||(!(tmp&1)&&ev.Que(nm2)>=tmp)))return 1;
	tmp=n2+tt-n1;
	if(tmp>=0&&(((tmp&1)&&od.Que(nm1)>=tmp)||(!(tmp&1)&&ev.Que(nm1)>=tmp)))return 1;
	return 0;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)scanf("%d",&p[i]),p[i]>mx?mx=p[i],tg[i]=1,++tt:0;
	for(int i=1;i<=n;++i)od.val[i]=-1e9;
	for(int i=n;i>=1;--i){
		++od.tim,++ev.tim;
		if(tg[i])od.Ins(p[i],od.Que(p[i])+2),ev.Ins(p[i],ev.Que(p[i])+2);
		else t1=od.Que(p[i]),t2=ev.Que(p[i]),od.Ins(p[i],t2+1),ev.Ins(p[i],t1+1);
	}
	nm1=nm2=1;
	if(!Check())return puts("-1"),0;
	for(int i=1;i<=n;++i){
		tt-=tg[i],od.Back(),ev.Back();
		n1+=(p[i]>=nm1);
		if(Check())putchar('0'),nm1=max(nm1,p[i]);
		else n1-=(p[i]>=nm1),n2+=(p[i]>=nm2),nm2=max(nm2,p[i]),putchar('1');
	}
	return 0;
}