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 clr(x) memset(x,0,sizeof x)
#define For(i,a,b) for (int i=(a);i<=(b);i++)
#define Fod(i,b,a) for (int i=(b);i>=(a);i--)
#define pb(x) push_back(x)
#define mp(x,y) make_pair(x,y)
#define fi first
#define se second
#define outval(x) cerr<<#x" = "<<x<<endl
#define outtag(x) cerr<<"-----------------"#x"-----------------\n"
#define outarr(a,L,R) cerr<<#a"["<<L<<".."<<R<<"] = ";\
                    For(_x,L,R) cerr<<a[_x]<<" ";cerr<<endl;
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair <int,int> pii;
namespace IO{
    const int S=1<<20;
    char I[S+1],*Is=I,*It=I;
    char gc(){return Is==It?((It=(Is=I)+fread(I,1,S,stdin))==I?EOF:*Is++):*Is++;}
    #define getchar gc
}
using namespace IO;
LL read(){
    LL x=0,f=0;
    char ch=getchar();
    while (!isdigit(ch))
        f=ch=='-',ch=getchar();
    while (isdigit(ch))
        x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return f?-x:x;
}
const int N=200005;
int n;
int a[N];
struct BIT{
	pair <int,int> c[N];
	void clear(){
		clr(c);
	}
	void Add(int x,pair <int,int> d){
		for (;x<=n;x+=x&-x)
			c[x]=max(c[x],d);
	}
	pair <int,int> Ask(int x){
		pair <int,int> ans=mp(0,0);
		for (;x;x-=x&-x)
			ans=max(ans,c[x]);
		return ans;
	}
}bit[2];
int pre[N],c=0;
int len[N][2];
pair <int,int> p[N][2];
int vis[N];
int main(){
	n=read();
	For(i,1,n){
		a[i]=read();
		pre[i]=max(pre[i-1],a[i]);
		c+=pre[i]!=pre[i-1];
	}
	bit[0].clear(),bit[1].clear();
	pair <int,int> res=mp(-1,-1);
	Fod(i,n,1){
		pair <int,int> l0=bit[0].Ask(n-(a[i]+1)+1);
		pair <int,int> l1=bit[1].Ask(n-(a[i]+1)+1);
		if (l1.se==0)
			l1.fi=-1e5;
		int flag=0;
		if (l0<l1)
			l0=l1,flag=1;
		if (a[i]==pre[i]){
			p[i][0]=mp(l0.se,flag);
			p[i][1]=mp(l1.se,1);
			len[i][0]=l0.fi+2;
			len[i][1]=l1.fi+2;
			bit[0].Add(n-a[i]+1,mp(l0.fi+2,i));
			bit[1].Add(n-a[i]+1,mp(l1.fi+2,i));
			if (len[i][0]==c&&!~res.fi)
				res=mp(i,0);
			if (len[i][1]>=c&&!~res.fi)
				res=mp(i,1);
		}
		else {
			p[i][0]=p[i][1]=mp(l0.se,flag);
			len[i][0]=len[i][1]=l0.fi+1;
			bit[0].Add(n-a[i]+1,mp(l0.fi+1,i));
			bit[1].Add(n-a[i]+1,mp(l0.fi+1,i));
			if (len[i][1]>=c&&!~res.fi)
				res=mp(i,1);
		}
	}
	string ans1="";
	if (res.se==-1){
		ans1="2";
	}
	else {
		clr(vis);
		int d=len[res.fi][res.se]-c,e=0;
		while (res.fi){
			vis[res.fi]=1;
			if (a[res.fi]!=pre[res.fi])
				e++;
			res=p[res.fi][res.se];
		}
		e=e/2*2;
		For(i,1,n)
			if (vis[i]){
				if (a[i]==pre[i]){
					if (d>=2)
						d-=2,vis[i]=0;
				}
				else {
					if (d>0&&e>0)
						d--,e--,vis[i]=0;
				}
			}
		int m0=0,m1=0;
		For(i,1,n)
			if (!vis[i]){
				if (a[i]==pre[i]){
					ans1+='0';
					m0=max(m0,a[i]);
				}
				else if (a[i]>m0){
					ans1+='1';
					m1=max(m1,a[i]);
				}
				else {
					ans1+='0';
					m0=max(m0,a[i]);
				}
			}
			else {
				ans1+='1';
				m1=max(m1,a[i]);
			}
	}
	
	string ans2="2";
	int premax=0,ned=c;
	clr(vis);
	For(i,1,n){
		if (a[i]>premax&&ned>=(a[i]==pre[i]?2:1)){
			if ((len[i][0]>=ned&&(len[i][0]-ned)%2==0)||len[i][1]>=ned){
				vis[i]=1;
				ned-=a[i]==pre[i]?2:1;
				premax=a[i];
			}
		}
	}
	if (ned==0){
		ans2="";
		int m0=0,m1=0;
		For(i,1,n)
			if (!vis[i]){
				if (a[i]==pre[i]){
					ans2+='1';
					m1=max(m1,a[i]);
				}
				else if (a[i]<m0){
					ans2+='0';
					m0=max(m0,a[i]);
				}
				else {
					ans2+='1';
					m1=max(m1,a[i]);
				}
			}
			else {
				ans2+='0';
				m0=max(m0,a[i]);
			}
	}
	string ans=min(ans1,ans2);
	if (ans[0]>'1')
		puts("-1");
	else {
		static char aa[N];
		For(i,0,n-1)
			aa[i]=ans[i];
		fwrite(aa,1,n,stdout);
	}
	return 0;
}