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 FR first
#define SE second
#define inf 0x3f3f3f3f

using namespace std;

typedef pair<int,int> pr;

namespace SGT {

const int Maxn=5000000;

int ch[Maxn][2],tot;
int max1[Maxn],max2[Maxn];

inline int cpynode(int o) {
  tot++;
  ch[tot][0]=ch[o][0];ch[tot][1]=ch[o][1];
  max1[tot]=max1[o];max2[tot]=max2[o];
  return tot;
}

inline void pushup(int o) {
  max1[o]=max(max1[ch[o][0]],max1[ch[o][1]]);
  max2[o]=max(max2[ch[o][0]],max2[ch[o][1]]);
}

int update(int l,int r,int o,int p,pr q) {
  o=cpynode(o);
  if (l==r) {
  	max1[o]=q.FR;max2[o]=q.SE;
  }
  else {
  	int m=((l+r)>>1);
  	if (m>=p) ch[o][0]=update(l,m,ch[o][0],p,q);
  	else ch[o][1]=update(m+1,r,ch[o][1],p,q);
  	pushup(o);
  }
  return o;
}

int query(int l,int r,int o,int p,bool q) {
  if (!o) return (!q)?0:-inf;
  if (l==r) return (!q)?max1[o]:max2[o];
  else {
  	int m=((l+r)>>1);
  	if (m<p) return query(m+1,r,ch[o][1],p,q);
  	else {
  		int t=query(l,m,ch[o][0],p,q);
  		return (!q)?max(t,max1[ch[o][1]]):max(t,max2[ch[o][1]]);
	  }
  }
}

}

int root[200005],num[200005];
bool tag[200005];

int pre(int n) {
  int s=0,maxn=0;
  for(int i=1;i<=n;i++)
    if (num[i]>maxn) {
    	maxn=num[i];
    	s++;
    	tag[i]=1;
	}
  for(int i=n;i>0;i--)
    if (tag[i]) {
    	int t1=SGT::query(1,n+1,root[i+1],num[i]+1,0),t2=SGT::query(1,n+1,root[i+1],num[i]+1,1);
    	root[i]=SGT::update(1,n+1,root[i+1],num[i],pr(t1+2,t2+2));
	}
	else {
		int t=SGT::query(1,n+1,root[i+1],num[i]+1,0);
		root[i]=SGT::update(1,n+1,root[i+1],num[i],pr(t+1,t+1));
	}
  return s;
}

int main() {
  SGT::max1[0]=0;SGT::max2[0]=-inf;
  int n;
  scanf("%d",&n);
  for(int i=1;i<=n;i++) scanf("%d",&num[i]);
  int s=pre(n);
  if ((s&1)&&SGT::query(1,n+1,root[1],1,1)<s) {
  	puts("-1");
  	return 0;
  }
  int r1=0,r2=0,d=0;
  for(int i=1;i<=n;i++) {
  	s-=tag[i];
  	int t=d+(num[i]>r1),c=max(r1,num[i]);
  	bool ok=1;
  	if ((t^s)&1) {
  		if (t>=0) {
  			if (SGT::query(1,n+1,root[i+1],r2+1,1)<s+t&&(t>s||SGT::query(1,n+1,root[i+1],c+1,1)<s-t)) ok=0;
		  }
		else {
			if (SGT::query(1,n+1,root[i+1],c+1,1)<s-t&&(-t>s||SGT::query(1,n+1,root[i+1],r2+1,1)<s+t)) ok=0;
		}
	  }
	else {
		if (t>=0) {
			if (SGT::query(1,n+1,root[i+1],r2+1,0)<s+t) ok=0;
		}
		else {
			if (SGT::query(1,n+1,root[i+1],c+1,0)<s-t) ok=0;
		}
	}
	if (ok) {
		putchar('0');
		d+=(num[i]>r1);
		r1=max(r1,num[i]);
	}
	else {
		putchar('1');
		d-=(num[i]>r2);
		r2=max(r2,num[i]);
	}
  }
  printf("\n");
  return 0;
}