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;

#define mp make_pair
#define ft first
#define sd second

const int maxN=202000;
const int inf=2000000000;

int Bodd[maxN],Beven[maxN];
int n,Seq[maxN],Mx[maxN],Sttop[maxN];
stack<pair<int*,int> > Rc;

void Modify(int *B,int p,int key);
int Query(int *B,int p);
bool check(int sum,int limit);
bool legal(int m0,int m1,int minus,int mxcnt);
int main(){
    int mxcnt=0;
    scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",&Seq[i]);
    for (int i=1,mx=0;i<=n;i++){
	Bodd[i]=-inf;Beven[i]=0;
	if (Seq[i]>mx) Mx[i]=1,mx=Seq[i],++mxcnt;
    }

    for (int i=n;i>=1;i--){
	//cerr<<i<<endl;
	int odd=-inf,even=-inf;Sttop[i]=Rc.size();
	if (Mx[i]){
	    odd=Query(Bodd,n-Seq[i]+1)+2;
	    even=Query(Beven,n-Seq[i]+1)+2;
	}
	else{
	    odd=Query(Beven,n-Seq[i]+1)+1;
	    even=Query(Bodd,n-Seq[i]+1)+1;
	}

	if (odd>=0) Modify(Bodd,n-Seq[i]+1,odd);
	if (even>=0) Modify(Beven,n-Seq[i]+1,even);
    }

    if (!check(mxcnt,1)){
	puts("-1");return 0;
    }

    int minus=0,mx0=1,mx1=1;
    for (int i=1;i<=n;i++){
	if (Mx[i]) --mxcnt;
	while (Rc.size()>Sttop[i]) *Rc.top().ft=Rc.top().sd,Rc.pop();
	if (Seq[i]>=mx0){
	    if (legal(Seq[i],mx1,minus+1,mxcnt)){
		printf("0");mx0=Seq[i];++minus;
	    }
	    else{
		printf("1");if (Seq[i]>=mx1) mx1=Seq[i],--minus;
	    }
	}
	else{
	    if (legal(mx0,mx1,minus,mxcnt)) printf("0");
	    else{
		printf("1");if (Seq[i]>=mx1) mx1=Seq[i],--minus;
	    }
	}
    }
    puts("");return 0;
}
void Modify(int *B,int p,int key){
    while (p<=n){
	if (B[p]<key){
	    Rc.push(mp(&B[p],B[p]));B[p]=key;
	}
	p+=(p)&(-p);
    }
    return;
}
int Query(int *B,int p){
    int ret=-inf;
    while (p){
	ret=max(ret,B[p]);p-=(p)&(-p);
    }
    return ret;
}
bool check(int sum,int limit){
    if (sum<0) return 0;
    if (sum&1) return sum<=Query(Bodd,n-limit+1);
    return sum<=Query(Beven,n-limit+1);
}
bool legal(int m0,int m1,int minus,int mxcnt){
    return check(mxcnt-minus,m0)||check(mxcnt+minus,m1);
}