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:
// Author -- Frame

#include<bits/stdc++.h>

#define lowbit(x) ((x)&(-(x)))
#define Finline __inline__ __attribute__ ((always_inline))
#define DEBUG fprintf(stderr,"Running on Line %d in Function %s\n",__LINE__,__FUNCTION__)
#define SZ(x) ((int)x.size())
#define mkpr std::make_pair
#define pb push_back

typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
typedef std::pair<int,int> pi;
typedef std::pair<ll,ll> pl;
using std::min;
using std::max;

const int inf=0x3f3f3f3f,Inf=0x7fffffff;
const ll INF=0x3f3f3f3f3f3f3f3f;

Finline uint rnd(){static uint seed=416;return seed^=seed>>5,seed^=seed<<17,seed^=seed>>13;}
template <typename _Tp>_Tp gcd(const _Tp &a,const _Tp &b){return (!b)?a:gcd(b,a%b);}
template <typename _Tp>Finline _Tp abs(const _Tp &a){return a>=0?a:-a;}
template <typename _Tp>Finline void chmax(_Tp &a,const _Tp &b){(a<b)&&(a=b);}
template <typename _Tp>Finline void chmin(_Tp &a,const _Tp &b){(b<a)&&(a=b);}
template <typename _Tp>Finline void read(_Tp &x)
{
	char ch(getchar());bool f(false);while(!isdigit(ch)) f|=ch==45,ch=getchar();
	x=ch&15,ch=getchar();while(isdigit(ch)) x=(((x<<2)+x)<<1)+(ch&15),ch=getchar();
	f&&(x=-x);
}
template <typename _Tp,typename... Args>Finline void read(_Tp &t,Args &...args){read(t);read(args...);}
template <typename _Tp,typename... Args>Finline _Tp min(const _Tp &a,const _Tp &b,const Args &...args){return a<b?min(a,args...):min(b,args...);}
template <typename _Tp,typename... Args>Finline _Tp max(const _Tp &a,const _Tp &b,const Args &...args){return a<b?max(b,args...):max(a,args...);}
Finline int read_str(char *s)
{
	char ch(getchar());while(ch==' '||ch=='\r'||ch=='\n') ch=getchar();
	char *tar=s;*tar=ch,ch=getchar();while(ch!=' '&&ch!='\r'&&ch!='\n'&&ch!=EOF) *(++tar)=ch,ch=getchar();
	return tar-s+1;
}

const int N=200005;
std::vector<std::pair<int*,int>> st;
struct BIT{
	int c[N];
	int add(int x,int C){int cnt=0;for(;x;x-=lowbit(x)) if(C>c[x]) st.pb(mkpr(c+x,c[x])),c[x]=C,++cnt;return cnt;}
	int sum(int x){int ans=-inf;for(;x<N;x+=lowbit(x))chmax(ans,c[x]);return ans;}
}tr[2];
Finline void reset()
{
	*st.back().first=st.back().second;
	st.pop_back();
}
int qwq[N];
int a[N],dp[N][2];
bool mark[N];
int suf[N],res[N];
int A[N],B[N];
int main()
{
	int n;read(n);
	for(int i=1;i<=n;++i) read(a[i]);
	int maxx=0;
	for(int i=1;i<=n;++i) if(a[i]>maxx) maxx=a[i],mark[i]=true;
	memset(tr[1].c,-63,sizeof(tr[1].c));
	for(int i=n;i>=1;--i)
	{
		suf[i]=suf[i+1]+(int)mark[i];
		if(mark[i]) for(int j=0;j<2;++j) dp[i][j]=tr[j].sum(a[i])+2;
		else for(int j=0;j<2;++j) dp[i][j]=tr[!j].sum(a[i])+1;
		for(int j=0;j<2;++j) qwq[i]+=tr[j].add(a[i],dp[i][j]);
	}
	int max1=0,max2=0,s1=0,s2=0,p1=0,p2=0;
	for(int i=1;i<=n;++i)
	{
		while(qwq[i]--) reset();
		int _s1=s1+(a[i]>max1),_max1=max(max1,a[i]);
		int tar=_s1-s2+suf[i+1];
		if(tar>=0&&tr[tar&1].sum(max2+1)>=tar) A[++p1]=a[i],s1=_s1,max1=_max1,res[i]=0;
		else
		{
			tar=s2-_s1+suf[i+1];
			if(tar>=0&&tr[tar&1].sum(_max1+1)>=tar) A[++p1]=a[i],s1=_s1,max1=_max1,res[i]=0;
			else B[++p2]=a[i],s2+=a[i]>max2,max2=max(max2,a[i]),res[i]=1;
		}
	}
	if(s1!=s2) printf("-1\n");
	else
	{
		for(int i=1;i<=n;++i) printf("%d",res[i]);
		printf("\n");
	}
	return 0;
}