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 N=2e5+5;
int n,p[N],x,y,mx0,mx1,ct0,ct1,i,w[N],cnt;
int bi[2][N];
pair<int,int*>op[N*40];int oxb,en[N];
inline void add(int o,int x,int v){
	for(x=n-x+1;x<=n;x+=x&-x)
		op[++oxb]=make_pair(bi[o][x],bi[o]+x),bi[o][x]=max(bi[o][x],v);
}
inline int ask(int o,int x){int ans=-N;for(x=n-x+1;x;x-=x&-x)ans=max(ans,bi[o][x]);return ans;}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);
	cin>>n;for(i=1;i<=n;++i){cin>>p[i];if(p[i]>x)w[i]=2,x=p[i],++cnt;else w[i]=1;}
	memset(bi[1],250,sizeof bi[1]);
	for(i=n;i;--i){
		x=ask(1,p[i]);y=ask(0,p[i]);
		if(x+w[i]<=cnt)add(1^(w[i]&1),p[i],x+w[i]);
		if(y+w[i]<=cnt)add(w[i]&1,p[i],y+w[i]);en[i]=oxb;
	}
	if(ask(cnt&1,1)!=cnt){cout<<"-1\n";return 0;}
	for(i=1;i<=n;++i){
		for(;oxb>en[i+1];)*op[oxb].second=op[oxb].first,--oxb;
		int nmx1=mx1,nct1=ct1;
		if(p[i]>nmx1)nmx1=p[i],++nct1;
		cnt-=w[i]==2;
		if((cnt+ct0-nct1>=0 && ask((cnt+ct0-nct1)&1,nmx1)>=cnt+ct0-nct1)
			 || (cnt+nct1-ct0>=0 && ask((cnt+nct1-ct0)&1,max(1,mx0))>=cnt+nct1-ct0))cout<<'0',mx1=nmx1,ct1=nct1;
			else{cout<<'1';if(p[i]>mx0)mx0=p[i],++ct0;}
	}
	cout<<endl;
	return 0;
}