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 mp make_pair
#define pb push_back
#define fi first
#define se second
#define sz(a) int(a.size())
#define clr(a) memset(a,0,sizeof(a))
#define all(a) a.begin(),a.end()
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;
const int inf=1e9;
const ll Inf=1e18;
const int N=2e5+10;
const int mod=0;
int gi() {
    int x=0,o=1;char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if(ch=='-') o=-1,ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*o;
}
template<typename T> bool chkmax(T &a,T b) { return a<b?a=b,1:0; };
template<typename T> bool chkmin(T &a,T b) { return a>b?a=b,1:0; };
int add(int a,int b) { return a+b>=mod?a+b-mod:a+b; }
int sub(int a,int b) { return a-b<0?a-b+mod:a-b; }
void inc(int &a,int b) { a=(a+b>=mod?a+b-mod:a+b); }
void dec(int &a,int b) { a=(a-b<0?a-b+mod:a-b); }
int n,mx=0,Q=0,vis[N],p[N],tr[2][N<<2],ans[N];
#define ls (o<<1)
#define rs (o<<1|1)
void modify(int o,int l,int r,int p,int f0,int f1) {
    if(l==r) { tr[0][o]=f0,tr[1][o]=f1;return; }
    int mid=(l+r)>>1;
    if(p<=mid) modify(ls,l,mid,p,f0,f1);
    else modify(rs,mid+1,r,p,f0,f1);
    for(int i=0;i<2;i++) tr[i][o]=max(tr[i][ls],tr[i][rs]);
}
int query(int k,int o,int l,int r,int p) {
    if(l==r) return tr[k][o];
    int mid=(l+r)>>1;
    if(p<=mid) return max(query(k,ls,l,mid,p),tr[k][rs]);
    else return query(k,rs,mid+1,r,p);
}
int check(int Hx,int Hy,int Cx,int Cy) {
    int t=Cx-Cy+Q;
    if(t>=0) {
        int mx=query(t&1,1,1,n,Hy);
        if(mx>=t) return 1;
    }
    t=Cy-Cx+Q;
    if(t>=0) {
        int mx=query(t&1,1,1,n,Hx);
        if(mx>=t) return 1;
    }
    return 0;
}
int main() {
    n=gi();
    for(int i=1;i<=n;i++) {
        p[i]=gi();
        chkmax(mx,p[i]);
        if(mx==p[i]) vis[i]=1,++Q;
    }
    for(int i=n;i;i--) {
        int f0=0,f1=0,t=query(0,1,1,n,p[i]);
        if(vis[i]) f0=t+2;
        else f1=t+1;
        t=query(1,1,1,n,p[i]);
        if(vis[i]) f1=t?t+2:0;
        else f0=t?t+1:0;
        modify(1,1,n,p[i],f0,f1);
    }
    int fl=1;
    int Hx=-inf,Hy=-inf,Cx=0,Cy=0;
    for(int i=1;i<=n;i++) {
        int _Hx=Hx,_Cx=Cx;
        if(vis[i]) --Q;
        modify(1,1,n,p[i],0,0);
        if(chkmax(Hx,p[i])) ++Cx;
        if(check(Hx,Hy,Cx,Cy)) continue;
        Hx=_Hx,Cx=_Cx,ans[i]=1;
        if(chkmax(Hy,p[i])) ++Cy;
        if(!check(Hx,Hy,Cx,Cy)) { fl=0;break; }
    }
    if(!fl) puts("-1");
    else {
        for(int i=1;i<=n;i++) putchar(ans[i]+'0');
    }
    return 0;
}