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<cctype>
#include<cstring>
#include<utility>
#include<algorithm>
#define fi first
#define se second
namespace IO
{
    char ibuf[(1<<21)+1],*iS,*iT;
    char Get(){return (iS==iT? (iT=(iS=ibuf)+fread(ibuf,1,(1<<21)+1,stdin),(iS==iT? EOF:*iS++)):*iS++);}
    int read(){int x=0,c=Get();while(!isdigit(c))c=Get();while(isdigit(c))x=x*10+c-48,c=Get();return x;}
}
using IO::read;
using std::pair;
using pi=pair<int,int>;
const int N=200007,M=5000007;
int n,a[N],val[N],sum[N],mx[2],mn[2][2],c[2][2];pi pos[N];
char ans[N];
struct BIT
{
    int t[N],top;pi stk[M];
    void add(int p,int v){for(;p<=n;p+=p&-p)stk[++top]={p,t[p]},t[p]=std::max(t[p],v);}
    int ask(int p){int r=-1e9;for(p=std::min(p,n);p;p^=p&-p)r=std::max(r,t[p]);return r;}
    void undo(int p){for(;top>p;--top)t[stk[top].fi]=stk[top].se;}
}t[2];
int main()
{
    n=read();
    for(int i=1,x=n+1;i<=n;++i) if(x>(a[i]=n+1-read())) x=a[i],val[i]=2; else val[i]=1;
    memset(t[1].t,0x8f,sizeof t[1].t);
    for(int i=n;i;--i) sum[i]=sum[i+1]+(val[i]==2);
    for(int i=n;i^1;--i)
    {
	for(int j=0;j<2;++j) mx[j]=std::max(0,t[j].ask(a[i]));
	for(int j=0,x;j<2;++j) x=mx[j]+val[i],t[x&1].add(a[i],x);
	pos[i]={t[0].top,t[1].top};
    }
    mn[0][0]=mn[0][1]=n+1;
    for(int i=1,now=0;i<=n;++i)
    {
    	now^=1;
        if(i<n)	t[0].undo(pos[i+1].fi),t[1].undo(pos[i+1].se);
	for(int j=0,f;j<2;++j)
	{
	    memcpy(mn[now],mn[now^1],8),memcpy(c[now],c[now^1],8);
	    if(a[i]<mn[now^1][j]) mn[now][j]=a[i],c[now][j]=c[now^1][j]+1;
	    f=i==n? (c[now][0]==c[now][1]):0;
	    if(i<n)
	    {
		for(int k=0,x;k<2;++k)
		{
		    x=c[now][k]-c[now][k^1]+sum[i+1];
		    if(x>=0&&x<=t[x&1].ask(mn[now][k^1])) {f=1;break;}
		}
	    }
	    if(f) {ans[i]='0'+j;break;}
    	}
    	if(!ans[i]) return !printf("-1");
    }
    for(int i=1;i<=n;++i) putchar(ans[i]);
}