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 ll long long
#define ull unsigned ll
#define uint unsigned
#define db long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define IT iterator
 
#define PB push_back
#define MK make_pair
#define LB lower_bound
#define UB upper_bound
#define EB emplace_back
#define fi first
#define se second
 
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define UPD(x,y) (((x)+=(y))>=mo?x-=mo:233)
#define CLR(a,v) memset(a,v,sizeof(a));
#define CPY(a,b) memcpy(a,b,sizeof(a));
 
#define LS3 k*2,l,mid
#define RS3 k*2+1,mid+1,r
#define LS5 k*2,l,mid,x,y
#define RS5 k*2+1,mid+1,r,x,y
#define GET pushdown(k);int mid=(l+r)/2
 
#define inf 2000000000
#define sqr(x) ((x)*(x))
using namespace std;
const int N=200005;
int p[N],t[N*4][2];
int n,Q,mx,a[N],vis[N],ans[N];
void change(int k,int l,int r,int p,int v0,int v1){
	if (l==r){
		t[k][0]=v0;
		t[k][1]=v1;
		return;
	}
	int mid=(l+r)/2;
	if (p<=mid) change(k*2,l,mid,p,v0,v1);
	else change(k*2+1,mid+1,r,p,v0,v1);
	t[k][0]=max(t[k*2][0],t[k*2+1][0]);
	t[k][1]=max(t[k*2][1],t[k*2+1][1]);
}
int ask(int fl,int k,int l,int r,int p){
	if (p<=l) return t[k][fl];
	int mid=(l+r)/2;
	if (p>mid) return ask(fl,k*2+1,mid+1,r,p);
	return max(ask(fl,k*2,l,mid,p),t[k*2+1][fl]);
}
bool check(int HX,int HY,int CX,int CY){
	int t=CX-CY+Q;
	if (t>=0&&ask(t&1,1,1,n,HY)>=t) return 1;
	t=CY-CX+Q;
	if (t>=0&&ask(t&1,1,1,n,HX)>=t) return 1;
	return 0;
}
int main(){
	scanf("%d",&n);
	For(i,1,n){
		scanf("%d",&a[i]);
		if (a[i]>mx) mx=a[i],vis[i]=1,++Q;
	}
	Rep(i,n,1){
		int f0=0,f1=0,t=ask(0,1,1,n,a[i]);
		vis[i]?f0=t+2:f1=t+1;
		t=ask(1,1,1,n,a[i]);
		vis[i]?(f1=(t?t+2:0)):(f0=(t?t+1:0));
		change(1,1,n,a[i],f0,f1);
	}
	bool fl=1;
	int HX=-(1<<30),HY=HX,CX=0,CY=0;
	For(i,1,n){
		int _HX=HX,_CX=CX;
		if (vis[i]) --Q;
		change(1,1,n,a[i],0,0);
		if (HX<a[i]) HX=a[i],++CX;
		if (check(HX,HY,CX,CY)) continue;
		HX=_HX; CX=_CX; ans[i]=1;
		if (HY<a[i]) HY=a[i],++CY;
		if (check(HX,HY,CX,CY)) continue;
		fl=0;
	}
	if (!fl) puts("-1");
	else For(i,1,n) putchar(ans[i]+'0');
}