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 <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int Q=1<<18;
int tl=0;
int ls[Q*36],rs[Q*36];
int mx[Q*36];
void MDF(int lst,int &now,int l,int r,int x,int v)
{
    now=++tl;
    mx[now]=-998244353;
    if(l==r){
        mx[now]=max(mx[now],v);
        return;
    }
    ls[now]=ls[lst],rs[now]=rs[lst];
    int mid=(l+r)>>1;
    if(x<=mid)MDF(ls[lst],ls[now],l,mid,x,v);
    else MDF(rs[lst],rs[now],mid+1,r,x,v);
    mx[now]=max(mx[ls[now]],mx[rs[now]]);
}
int GM(int now,int l,int r,int x,int y)
{
    if(x<=l&&y>=r)return mx[now];
    int mid=(l+r)>>1;
    if(y<=mid)return GM(ls[now],l,mid,x,y);
    if(x>mid)return GM(rs[now],mid+1,r,x,y);
    return max(GM(ls[now],l,mid,x,y),GM(rs[now],mid+1,r,x,y));
}
int rt0[Q],rt1[Q];
int p[Q];
int imp[Q];
int n;
int c0=0,c1=0;
int res=0;
int mxa,mxb;
int Ch(int st)
{
    int ra=c0-c1+res,rb=c1-c0+res;
    int pa=GM((ra&1?rt1:rt0)[st],1,n,mxb,n),pb=GM((rb&1?rt1:rt0)[st],1,n,mxa,n);
    if(ra>=0&&pa>=ra)return 1;
    if(rb>=0&&pb>=rb)return 1;
    return 0;
}
void Ga(int x)
{
    if(imp[x])--res;
}
int main()
{
    mx[0]=-998244353;
    scanf("%d",&n);
    for(int i=1,mx=0;i<=n;i++){
        scanf("%d",&p[i]);
        if(mx<p[i])mx=p[i],imp[i]=1,++res;
    }
    MDF(rt0[n+1],rt0[n+1],1,n,n,0);
    for(int i=n;i;--i){
        int f0=GM(rt0[i+1],1,n,p[i],n)+imp[i]+1;
        int f1=GM(rt1[i+1],1,n,p[i],n)+imp[i]+1;
        // printf("%d %d ???\n",imp[i]?f0:f1,imp[i]?f1:f0);
        MDF(rt0[i+1],rt0[i],1,n,p[i],imp[i]?f0:f1);
        MDF(rt1[i+1],rt1[i],1,n,p[i],imp[i]?f1:f0);
    }
    if(!Ch(1))return puts("-1")&0;
    mxb=0,mxa=0;
    for(int i=1;i<=n;i++){
        int cc=c0,ra=mxa;
        if(imp[i])--res;
        if(p[i]>mxa)++c0,mxa=p[i];
        int fin=Ch(i+1);
        if(!fin){
            c0=cc;mxa=ra;
            if(p[i]>mxb)mxb=p[i],++c1;
            putchar('1');
        }
        else putchar('0');
    }
    return 0;
}
/*
c0+(tl-k)==c1+k+had
c0-c1+tl==2*k+had;
*/