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 pii pair<int,int>
#define pll pair<ll,ll>
#define PB push_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 CLR(a,v) memset(a,v,sizeof(a));
#define CPY(a,b) memcpy(a,b,sizeof(a));
using namespace std;
const int N=200005;
int n,mx,Q,a[N];
int vis[N],ans[N];
struct TREE{
	int t[N*4],nn;
	void build(int n){
		for (nn=1;nn<=n+1;nn<<=1);
	}
	void change(int x,int v){
		x+=nn; t[x]=v;
		for (x>>=1;x;x>>=1)
			t[x]=max(t[x<<1],t[x<<1|1]);
	}
	int ask(int x){
		x+=nn-(x!=0);
		int ans=0;
		for (;x^1;x>>=1)
			if (!(x&1)) ans=max(ans,t[x^1]);
		return ans;
	}
}T[2];
bool check(int HX,int HY,int CX,int CY){
	int tmp=CX-CY+Q;
	if (tmp>=0&&T[tmp&1].ask(HY)>=tmp) return 1;
	tmp=CY-CX+Q;
	if (tmp>=0&&T[tmp&1].ask(HX)>=tmp) return 1;
	return 0;
}
int main(){
	scanf("%d",&n);
	T[0].build(n);
	T[1].build(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 t=T[0].ask(a[i]);
		int v0=0,v1=0;
		vis[i]?v0=t+2:v1=t+1;
		t=T[1].ask(a[i]);
		if (t) vis[i]?v1=t+2:v0=t+1;
		T[0].change(a[i],v0);
		T[1].change(a[i],v1);
	}
	int HX=0,HY=HX,CX=0,CY=0,fl=1;
	For(i,1,n){
		if (vis[i]) --Q;
		T[0].change(a[i],0);
		T[1].change(a[i],0);
		int _HX=HX,_CX=CX;
		if (a[i]>HX) HX=a[i],++CX;
		if (check(HX,HY,CX,CY)) continue;
		HX=_HX; CX=_CX; ans[i]=1;
		if (a[i]>HY) HY=a[i],++CY;
		if (check(HX,HY,CX,CY)) continue;
		fl=0;
	}
	if (!fl) puts("-1");
	else For(i,1,n) putchar('0'+ans[i]);
}