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>
using namespace std;
#define MAX 200200
inline int read()
{
    int x=0;bool t=false;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=true,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return t?-x:x;
}
int n,a[MAX],val[MAX],cnt[MAX];
char s[MAX];
struct SegmentTree
{
#define lson (now<<1)
#define rson (now<<1|1)
    int t[MAX<<2];
    void Build(int now,int l,int r)
    {
        if(l==r){t[now]=-1e9;return;}
        int mid=(l+r)>>1;
        Build(lson,l,mid);Build(rson,mid+1,r);
        t[now]=max(t[lson],t[rson]);
    }
    void Modify(int now,int l,int r,int p,int w)
    {
        if(l==r){t[now]=w;return;}
        int mid=(l+r)>>1;
        if(p<=mid)Modify(lson,l,mid,p,w);
        else Modify(rson,mid+1,r,p,w);
        t[now]=max(t[lson],t[rson]);
    }
    int Query(int now,int l,int r,int L,int R)
    {
        if(L<=l&&r<=R)return t[now];
        int mid=(l+r)>>1,ret=-1e9;
        if(L<=mid)ret=max(ret,Query(lson,l,mid,L,R));
        if(R>mid)ret=max(ret,Query(rson,mid+1,r,L,R));
        return ret;
    }
}Odd,Even;
bool check(int mx,int Q)
{
    if(Q<0)return false;
    if(Q&1)return Odd.Query(1,1,n,mx,n)>=Q;
    else return Even.Query(1,1,n,mx,n)>=Q;
}
int main()
{
    n=read();
    for(int i=1,mx=0;i<=n;++i)
    {
        a[i]=read();
        if(a[i]>mx)val[i]=2,mx=a[i];
        else val[i]=1;
    }
    Odd.Build(1,1,n);
    for(int i=n;i;--i)
    {
        int mx1=Odd.Query(1,1,n,a[i],n),mx0=Even.Query(1,1,n,a[i],n);
        if(val[i]&1)Odd.Modify(1,1,n,a[i],mx0+val[i]),Even.Modify(1,1,n,a[i],mx1+val[i]);
        else Odd.Modify(1,1,n,a[i],mx1+val[i]),Even.Modify(1,1,n,a[i],mx0+val[i]);
    }
    for(int i=n;i;--i)cnt[i]=cnt[i+1]+val[i]-1;
    int cntX=0,cntY=0,mxX=0,mxY=0;
    for(int i=1;i<=n;++i)
    {
        Odd.Modify(1,1,n,a[i],-1e9);Even.Modify(1,1,n,a[i],0);
        if(check(mxY,cntX+cnt[i+1]-cntY+(a[i]>mxX)))s[i]='0',cntX+=a[i]>mxX,mxX=max(mxX,a[i]);
        else if(check(max(mxX,a[i]),cntY+cnt[i+1]-cntX-(a[i]>mxX)))s[i]='0',cntX+=a[i]>mxX,mxX=max(mxX,a[i]);
        else s[i]='1',cntY+=a[i]>mxY,mxY=max(mxY,a[i]);
    }
    if(cntX!=cntY){puts("-1");}
    else printf("%s",s+1);
    return 0;
}