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;

const int maxn=2e5+10;
int n,p[maxn],sum[maxn];
char ans[maxn];

inline void init(){
	for(int i=1,top=0;i<=n;++i)
		if(p[i]>top)
			sum[i]=sum[i-1]+1,top=p[i];
		else
			sum[i]=sum[i-1];
}
namespace segt{
	const int size=maxn*20;
	int cnt,root[maxn];
	int odd[size],even[size],lson[size],rson[size];
	inline void init(){
		odd[cnt]=-1e9;
		even[cnt]=0;
	}
	inline int newnode(int rt){
		++cnt;
		odd[cnt]=odd[rt];
		even[cnt]=even[rt];
		lson[cnt]=lson[rt];
		rson[cnt]=rson[rt];
		return cnt;
	}
	void query(int rt,int l,int r,int x,int&reso,int&rese){
		if(l==x){
			if(reso<odd[rt])
				reso=odd[rt];
			if(rese<even[rt])
				rese=even[rt];
			return;
		}
		int mid=l+r>>1;
		if(x<=mid)
			query(lson[rt],l,mid,x,reso,rese),query(rson[rt],mid+1,r,mid+1,reso,rese);
		else
			query(rson[rt],mid+1,r,x,reso,rese);
	}
	int modify(int rt,int l,int r,int x,int valo,int vale){
		rt=newnode(rt);
		if(odd[rt]<valo)
			odd[rt]=valo;
		if(even[rt]<vale)
			even[rt]=vale;
		if(l==r)
			return rt;
		int mid=l+r>>1;
		if(x<=mid)
			lson[rt]=modify(lson[rt],l,mid,x,valo,vale);
		else
			rson[rt]=modify(rson[rt],mid+1,r,x,valo,vale);
		return rt;
	}
	inline void run(){
		init();
		for(int i=n,o,e;i;--i){
			o=-1e9;e=0;
			query(root[i+1],1,n,p[i],o,e);
			if(sum[i]==sum[i-1])
				root[i]=modify(root[i+1],1,n,p[i],e+1,o+1);
			else
				root[i]=modify(root[i+1],1,n,p[i],o+2,e+2);
		}
	}
}
inline bool check(int pos,int numx,int numy,int maxx,int maxy){
	int odd,even,res;
	odd=-1e9;even=0;
	if(maxy<n)segt::query(segt::root[pos],1,n,maxy+1,odd,even);
	if(numx-numy+sum[n]-sum[pos-1]>=0&&(numx-numy+sum[n]-sum[pos-1]&1?odd:even)>=numx-numy+sum[n]-sum[pos-1])
		return true;
	odd=-1e9;even=0;
	if(maxx<n)segt::query(segt::root[pos],1,n,maxx+1,odd,even);
	if(numy-numx+sum[n]-sum[pos-1]>=0&&(numy-numx+sum[n]-sum[pos-1]&1?odd:even)>=numy-numx+sum[n]-sum[pos-1])
		return true;
	return false;
}

int main(){
	cin>>n;
	for(int i=1;i<=n;++i)
		cin>>p[i];
	init();
	segt::run();
	if(check(1,0,0,0,0)){
		for(int i=1,numx=0,numy=0,maxx=0,maxy=0;i<=n;++i)
			if(p[i]>maxx?check(i+1,numx+1,numy,p[i],maxy):check(i+1,numx,numy,maxx,maxy)){
				ans[i]='0';
				if(p[i]>maxx)
					++numx,maxx=p[i];
			}
			else{
				ans[i]='1';
				if(p[i]>maxy)
					++numy,maxy=p[i];
			}
		puts(ans+1);
	}
	else
		puts("-1");
	return 0;
}