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 fi first
#define se second
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define MAXN 200005
//#define ivorysi
#define space putchar(' ')
#define enter putchar('\n')
using namespace std;
typedef long long int64;
template<class T>
void read(T &res) {
    res = 0;char c = getchar();T f = 1;
    while(c < '0' || c > '9') {
	if(c == '-') f = -1;
	c = getchar();
    }
    while(c >= '0' && c <= '9') {
	res = res * 10 + c - '0';
	c = getchar();
    }
    res *= f;
}
template<class T>
void out(T x) {
    if(x < 0) {x = -x;}
    if(x >= 10) {
	out(x / 10);
    }
    putchar('0' + x % 10);
}
int N,P[MAXN],val[MAXN],ans[MAXN],curx,cury;
struct node {
    int maxv,L,R,lc,rc;
}tr[MAXN * 20];
int rt[2],Ncnt;
void build(int &u,int L,int R,int v) {
    u = ++Ncnt;
    tr[u].L = L;tr[u].R = R;
    tr[u].maxv = v;
    if(L == R) return;
    int mid = (L + R) >> 1;
    build(tr[u].lc,L,mid,v);
    build(tr[u].rc,mid + 1,R,v);
}
void Change(int u,int pos,int v) {
    if(tr[u].L == tr[u].R) {tr[u].maxv = v;return;}
    int mid = (tr[u].L + tr[u].R) >> 1;
    if(pos <= mid) Change(tr[u].lc,pos,v);
    else Change(tr[u].rc,pos,v);
    tr[u].maxv = max(tr[tr[u].lc].maxv,tr[tr[u].rc].maxv);
}
int Query(int u,int l,int r) {
    if(tr[u].L == l && tr[u].R == r) return tr[u].maxv;
    int mid = (tr[u].L + tr[u].R) >> 1;
    if(r <= mid) return Query(tr[u].lc,l,r);
    else if(l > mid) return Query(tr[u].rc,l,r);
    else return max(Query(tr[u].lc,l,mid),Query(tr[u].rc,mid + 1,r));
}
void Solve() {
    read(N);
    for(int i = 1 ; i <= N ; ++i) read(P[i]);
    int cur = 0,Q = 0;
    for(int i = 1 ; i <= N ; ++i) {
	cur = max(cur,P[i]);
	if(cur == P[i]) {val[i] = 2;++Q;}
	else val[i] = 1;
    }
    build(rt[0],1,N + 1,0);build(rt[1],1,N + 1,-2 * N);
    for(int i = N ; i >= 1 ; --i) {
	int tmp[2];
	for(int j = 0 ; j < 2 ; ++j) tmp[j] = Query(rt[j],P[i] + 1,N + 1);
	for(int j = 0 ; j < 2 ; ++j) {
	    if(tmp[j] + val[i] > 0) {
		int t = (tmp[j] + val[i]) & 1;
		Change(rt[t],P[i],tmp[j] + val[i]);
	    }
	}
    }
    int len[2] = {0,0},mx_num[2] = {0,0};
    for(int i = 1 ; i <= N ; ++i) {
	ans[i] = -1;
	Change(rt[0],P[i],0);Change(rt[1],P[i],-2 * N);
	if(val[i] == 2) --Q;
	for(int k = 0 ; k < 2 ; ++k) {
	    int nxt_len[2],nxt_mx_num[2];
	    memcpy(nxt_len,len,sizeof(len));
	    memcpy(nxt_mx_num,mx_num,sizeof(mx_num));
	    nxt_mx_num[k] = max(nxt_mx_num[k],P[i]);
	    if(nxt_mx_num[k] == P[i]) ++nxt_len[k];
	    if(i == N) {
		if(nxt_len[0] == nxt_len[1]) {ans[i] = k;break;}
		continue;
	    }
	    bool flag = 0;
	    
	    for(int j = 0 ; j < 2 ; ++j) {
		int t = nxt_len[j] - nxt_len[j ^ 1] + Q;
		if(t >= 0 && Query(rt[t & 1],nxt_mx_num[j ^ 1] + 1,N + 1) >= t) {flag = 1;break;}
	    }
	    if(flag) {
		ans[i] = k;
		memcpy(len,nxt_len,sizeof(len));
		memcpy(mx_num,nxt_mx_num,sizeof(mx_num));
		break;
	    }
	}
	if(ans[i] < 0) {
	    puts("-1");return;
	}
    }
    for(int i = 1 ; i <= N ; ++i) putchar('0' + ans[i]);
    enter;
}
int main() {
#ifdef ivorysi
    freopen("f1.in","r",stdin);
#endif
    Solve();
}