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<iostream> 
#include<cstdio> 
#include<algorithm> 
#include<cstring> 

using namespace std; 

const int maxn = 4e5+5; 
const int inf = 0x3f3f3f3f; 
int n; 
int a[maxn]; 
int h[maxn]; 
int rt,ls[maxn],rs[maxn],tot,mx[2][maxn]; 

void maketree(int &p,int l,int r) { 
	p = ++tot;
	mx[0][p] = mx[1][p] = -inf; 
    if(l==r) { 
        return; 
    } 
    int mid = (l+r)>>1; 
    maketree(ls[p],l,mid); 
    maketree(rs[p],mid+1,r); 
} 
void update(int ii,int &p,int l,int r,int x,int dd) { 
    if(l==r) { 
        mx[ii][p] = dd; 
        return; 
    } 
    int mid = (l+r)>>1; 
    if(x<=mid) update(ii,ls[p],l,mid,x,dd); 
    else if(x>mid) update(ii,rs[p],mid+1,r,x,dd); 
    mx[ii][p] = max(mx[ii][ls[p]],mx[ii][rs[p]]); 
} 
int query(int ii,int p,int l,int r,int x,int y) {
	if(x<=l&&r<=y) return mx[ii][p];
	int mid = (l+r)>>1;
	if(y<=mid) return query(ii,ls[p],l,mid,x,y);
	else if(x>mid) return query(ii,rs[p],mid+1,r,x,y);
	else return max(query(ii,ls[p],l,mid,x,y),query(ii,rs[p],mid+1,r,x,y));
}
bool isok(int cnt0,int cnt1,int max0,int max1,int NH) { 
    int yoo = (cnt1-cnt0+NH);
    if(yoo>=0&&query(yoo&1,rt,0,n+1,max0+1,n+1)>=yoo) return 1;
	yoo = cnt0-cnt1+NH;
	if(yoo>=0&&query(yoo&1,rt,0,n+1,max1+1,n+1)>=yoo) return 1;
	return 0;
} 
int main() { 
    int NH = 0; 
    scanf("%d",&n); 
    int MX = 0; 
    for(int i=1;i<=n;i++) { 
        scanf("%d",&a[i]); 
        MX = max(MX,a[i]); 
        h[i] = (a[i]==MX); 
        if(h[i]) NH++; 
    } 
    maketree(rt,0,n+1); 
    update(0,rt,0,n+1,n+1,0); 
    for(int i=n;i>=1;i--) { 
        int r0 = query(0,rt,0,n+1,a[i]+1,n+1); 
        int r1 = query(1,rt,0,n+1,a[i]+1,n+1); 
        if(h[i]) { 
            update(0,rt,0,n+1,a[i],r0+2); 
            update(1,rt,0,n+1,a[i],r1+2);             
        } else { 
            update(0,rt,0,n+1,a[i],r1+1); 
            update(1,rt,0,n+1,a[i],r0+1);             
        } 
    //	cerr<<r0<<' '<<r1<<endl;
    } 
    int cnt0 = 0 , cnt1 = 0 , max0 = 0 ,max1 = 0; 
    if(!isok(cnt0,cnt1,max0,max1,NH)) { 
        puts("-1"); return 0; 
    } 
    for(int i=1;i<=n;i++) { 
        update(0,rt,0,n+1,a[i],-inf); 
        update(1,rt,0,n+1,a[i],-inf);
        NH -= h[i]; 
        if(isok(cnt0+(a[i]>max0),cnt1,max(max0,a[i]),max1,NH)) { 
            cnt0 = cnt0 + (a[i]>max0);
            max0 = max(max0,a[i]); 
            putchar('0'); 
        } else { 
            cnt1 = cnt1 + (a[i]>max1); 
            max1 = max(max1,a[i]); 
            putchar('1'); 
        }
    } 
}