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;
namespace io{
    const int l=1<<20;
    char buf[l],*s,*t,c;
    inline void gc(){
        if(s==t){
            t=(s=buf)+fread(buf,1,l,stdin);
            c=s==t?EOF:*s++;
        }else c=*s++;
    }
    template<class IT>inline void gi(IT &x){
        x=0;gc();while(c<'0'||c>'9')gc();
        while('0'<=c&&c<='9'){x=(x<<1)+(x<<3)+(c^48);gc();}
    }
    char buf0[20];int a;
    template<class IT>inline void pi(IT x){
        if(x<0){putchar('-');x=-x;}
        do buf0[++a]=x%10+48;while(x/=10);
        while(a)putchar(buf0[a--]);
        putchar('\n');
    }
};
using io::gi;
using io::pi;
typedef unsigned int ui;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<int,ll > pil;
typedef pair<ll ,int> pli;
typedef pair<ll ,ll > pll;
typedef vector<int> vi;
typedef vector<ll > vl;
#define pque priority_queue
#define rep(i,l,r) for(i=(l);i<=(r);++i)
#define per(i,l,r) for(i=(l);i>=(r);--i)
#define REP(i,l,r) for(i=(l);i< (r);++i)
#define PER(i,l,r) for(i=(l);i> (r);--i)
#define mp make_pair
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define fi first
#define se second
template<class IT>inline void cmax(IT &a,IT b){if(a<b)a=b;}
template<class IT>inline void cmin(IT &a,IT b){if(b<a)a=b;}
const int N=200005;
struct node{
	pii v;
	int lc,rc;
}tre[N*19];int tot;
inline pii aww(pii a,int b){
	return (b&1)?mp(max(a.fi,a.se+b),max(a.se,a.fi+b)):mp(a.fi+b,a.se+b);
}
inline bool get(pii a,int b){return b>=0&&((b&1)?(b<=a.se):(b<=a.fi));}
inline pii pmax(pii a,const pii &b){cmax(a.fi,b.fi);cmax(a.se,b.se);return a;}
#define mid ((l+r)>>1)
#define ls tre[o].lc,l,mid
#define rs tre[o].rc,mid+1,r
void add(int O,int &o,int l,int r,int x,pii y){
	tre[o=++tot].v=pmax(tre[O].v,y);
	if(l==r)return;
	if(x<=mid){
		tre[o].rc=tre[O].rc;
		add(tre[O].lc,ls,x,y);
	}else{
		tre[o].lc=tre[O].lc;
		add(tre[O].rc,rs,x,y);
	}
}
pii que(int o,int l,int r,int x){
	if(l==r)return tre[o].v;
	if(x<=mid)return pmax(que(ls,x),tre[tre[o].rc].v);
	return que(rs,x);
}
int rt[N],a[N],h[N],s[N];
int main(){
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
	tre[0].v.se=-(N<<1|1);
    int n,i,cx=0,mx=0,cy=0,my=0,C,M,b;
    scanf("%d",&n);
    rep(i,1,n){
		scanf("%d",&a[i]);
		if(a[i]>mx){mx=a[i];h[i]=1;}
	}
	mx=0;
	per(i,n,1)add(rt[i+1],rt[i],1,n,a[i],aww(que(rt[i+1],1,n,a[i]),1+h[i]));
	per(i,n,1)s[i]=h[i]+s[i+1];
	if(!get(tre[rt[1]].v,s[1])){puts("-1");return 0;}
	rep(i,1,n){
		C=cx+(a[i]>mx);M=max(mx,a[i]);
		//printf("Y (%d,%d) %d\n",que(rt[i+1],1,n,my).fi,que(rt[i+1],1,n,my).se,C-cy+s[i+1]);
		//printf("X (%d,%d) %d\n",que(rt[i+1],1,n,M ).fi,que(rt[i+1],1,n,M ).se,cy-C+s[i+1]);
		if(get(que(rt[i+1],1,n,my),C-cy+s[i+1])||get(que(rt[i+1],1,n,M),cy-C+s[i+1]))
		{cx=C;mx=M;putchar('0');}else{cy+=(a[i]>my);cmax(my,a[i]);putchar('1');}
	}
    return 0;
}