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;

using ll=int64_t;
#define int ll

#define FOR(i,a,b) for(int i=int(a);i<int(b);i++)
#define REP(i,b) FOR(i,0,b)
#define MP make_pair
#define PB push_back
#define ALL(x) x.begin(),x.end()
#ifdef LOCAL
#define cerr (cerr<<"-- line "<<__LINE__<<" -- ")
#else
class CerrDummy{}cerrDummy;
template<class T>
CerrDummy& operator<<(CerrDummy&cd,const T&){
	return cd;
}
using charTDummy=char;
using traitsDummy=char_traits<charTDummy>;
CerrDummy& operator<<(CerrDummy&cd,basic_ostream<charTDummy,traitsDummy>&(basic_ostream<charTDummy,traitsDummy>&)){
	return cd;
}
#define cerr cerrDummy
#endif
#define REACH cerr<<"reached"<<endl
#define DMP(x) cerr<<#x<<":"<<x<<endl
#define ZERO(x) memset(x,0,sizeof(x))
#define ONE(x) memset(x,-1,sizeof(x))

using pi=pair<int,int>;
using vi=vector<int>;
using ld=long double;

template<class T,class U>
ostream& operator<<(ostream& os,const pair<T,U>& p){
	os<<"("<<p.first<<","<<p.second<<")";
	return os;
}

template<class T>
ostream& operator <<(ostream& os,const vector<T>& v){
	os<<"{";
	REP(i,(int)v.size()){
		if(i)os<<",";
		os<<v[i];
	}
	os<<"}";
	return os;
}

ll read(){
	ll i;
	scanf("%"  SCNd64,&i);
	return i;
}

void printSpace(){
	printf(" ");
}

void printEoln(){
	printf("\n");
}

void print(ll x,int suc=1){
	printf("%" PRId64,x);
	if(suc==1)
		printEoln();
	if(suc==2)
		printSpace();
}

string readString(){
	static char buf[3341000];
	scanf("%s",buf);
	return string(buf);
}

char* readCharArray(){
	static char buf[3341000];
	static int bufUsed=0;
	char* ret=buf+bufUsed;
	scanf("%s",ret);
	bufUsed+=strlen(ret)+1;
	return ret;
}

template<class T,class U>
void chmax(T& a,U b){
	if(a<b)
		a=b;
}

template<class T,class U>
void chmin(T& a,U b){
	if(b<a)
		a=b;
}

template<class T>
T Sq(const T& t){
	return t*t;
}

#define CAPITAL
void Yes(bool ex=true){
	#ifdef CAPITAL
	cout<<"YES"<<endl;
	#else
	cout<<"Yes"<<endl;
	#endif
	if(ex)exit(0);
}
void No(bool ex=true){
	#ifdef CAPITAL
	cout<<"NO"<<endl;
	#else
	cout<<"No"<<endl;
	#endif
	if(ex)exit(0);
}

const ll infLL=LLONG_MAX/3;

#ifdef int
const int inf=infLL;
#else
const int inf=INT_MAX/2-100;
#endif

struct SegTree{
	int s;
	vi buf;
	void Init(int n){
		s=1;
		while(s<n)s*=2;
		buf.resize(s*2,-inf);
	}
	void Set(int i,int v){
		i+=s;
		buf[i]=v;
		while(i>>=1)
			buf[i]=max(buf[i*2],buf[i*2+1]);
	}
	int Get(int b,int e,int l,int r,int i){
		if(e<=l||r<=b)
			return -inf;
		if(b<=l&&r<=e)
			return buf[i];
		return max(Get(b,e,l,(l+r)/2,i*2),Get(b,e,(l+r)/2,r,i*2+1));
	}
	int Get(int b,int e){
		if(e<=b)return -inf;
		return Get(b,e,0,s,1);
	}
};
signed main(){
	int n=read();
	vi p(n);
	REP(i,n)
		p[i]=read()-1;
	
	vi high(n,0);
	int highCnt=0;
	{
		int h=-1;
		REP(i,n)
			if(h<p[i]){
				h=p[i];
				high[i]=1;
				highCnt++;
			}
	}
	
	SegTree seg[2];
	REP(k,2)
		seg[k].Init(n+1);
	seg[0].Set(n,0);
	
	for(int i=n-1;i>=0;i--){
		int w=high[i]+1;
		REP(k,2){
			int x=seg[k].Get(p[i]+1,n+1);
			seg[(k+w)%2].Set(p[i],x+w);
		}
	}
	
	if(seg[highCnt%2].Get(0,n+1)<highCnt){
		cout<<-1<<endl;
		return 0;
	}
	
	string ans(n,'0');
	int c[2]{},h[2]{-1,-1};
	REP(i,n){
		int tmpC=c[0],tmpH=h[0];
		if(h[0]<p[i]){
			h[0]=p[i];
			c[0]++;
		}
		if(high[i])
			highCnt--;
		REP(k,2)
			seg[k].Set(p[i],-inf);
		bool ok=false;
		REP(k,2){
			int t=c[k^1]-c[k]+highCnt;
			if(t<0)continue;
			if(t<=seg[t%2].Get(h[k]+1,n+1)){
				ok=true;
				break;
			}
		}
		if(!ok){
			c[0]=tmpC,h[0]=tmpH;
			if(h[1]<p[i]){
				h[1]=p[i];
				c[1]++;
			}
			ans[i]='1';
		}
	}
	cout<<ans<<endl;
}