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;
const int inf=0x3f3f3f3f;
int n;
int nu[200200];
struct SEG{
    int ma[2000200];
    void build(int rt,int l,int r)
    {
        ma[rt]=-inf;
        if(l==r)return;
        int mid=(l+r)/2;
        build(rt*2,l,mid);
        build(rt*2+1,mid+1,r);
    }
    void change(int rt,int l,int r,int p,int v)
    {
        if(l==r){ma[rt]=v;return;}
        int mid=(l+r)/2;
        if(mid>=p)change(rt*2,l,mid,p,v);
        else change(rt*2+1,mid+1,r,p,v);
        ma[rt]=max(ma[rt*2],ma[rt*2+1]);
    }
    int query(int rt,int l,int r,int st,int ed)
    {
        if(l>ed||r<st)return -inf;
        if(l>=st&&r<=ed)return ma[rt];
        int mid=(l+r)/2;
        return max(query(rt*2,l,mid,st,ed),query(rt*2+1,mid+1,r,st,ed));
    }
}seg[2];
int val[200200];
int cnt[200200];
char ans[200200];
bool check(int v,int c)
{
    if(c<0)return 0;
    return seg[c&1].query(1,1,n,v,n)>=c;
}
int main()
{
    scanf("%d",&n);
    int mx=0;
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&nu[i]);
        val[i]=1;
        if(nu[i]>mx)val[i]++,mx=nu[i];
    }
    seg[1].build(1,1,n);
    int m0,m1;
    for(int i=n;i;--i)
    {
        cnt[i]=cnt[i+1]+val[i]-1;
        m0=seg[0].query(1,1,n,nu[i],n);
        m1=seg[1].query(1,1,n,nu[i],n);
        if(val[i]==2)
        {
            seg[0].change(1,1,n,nu[i],m0+2);
            seg[1].change(1,1,n,nu[i],m1+2);
        }
        else
        {
            seg[0].change(1,1,n,nu[i],m1+1);
            seg[1].change(1,1,n,nu[i],m0+1);
        }
    }
    int lx=0,ly=0;
    mx=0;int my=0;
    for(int i=1;i<=n;++i)
    {
        seg[0].change(1,1,n,nu[i],0);
        seg[1].change(1,1,n,nu[i],-inf);
        if(check(my,lx+(nu[i]>mx)+cnt[i+1]-ly))ans[i]='0';
        else if(check(max(mx,nu[i]),ly+cnt[i+1]-lx-(nu[i]>mx)))ans[i]='0';
        else ans[i]='1';
        if(ans[i]=='0')lx+=(nu[i]>mx),mx=max(mx,nu[i]);
        else ly+=(nu[i]>my),my=max(my,nu[i]);
    }
    if(lx!=ly)
    {
        puts("-1");
        return 0;
    }
    printf("%s\n",ans+1);
    return 0;
}