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:
//Zory-2019
#include<cmath>
#include<ctime>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<map>
#include<set>
#include<queue>
#include<deque>
#include<stack>
#include<bitset>
#include<vector>
#include<algorithm>
#include<iostream>
#include<deque>
using namespace std;
namespace mine
{
	typedef long long ll;
	#define double long double
	const int INF=0x3f3f3f3f;
	const ll LLINF=0x3f3f3f3f3f3f3f3fll;
	ll qread()
	{
		ll ans=0;char c=getchar();int f=1;
		while(c<'0' or c>'9') {if(c=='-') f=-1;c=getchar();}
		while('0'<=c and c<='9') ans=ans*10+c-'0',c=getchar();
		return ans*f;
	}
	void write(ll num)
	{
		if(num<0) {num=-num;putchar('-');}
		if(num>9) write(num/10);
		putchar('0'+num%10);
	}
	void write1(ll num){write(num);putchar(' ');}
	void write2(ll num){write(num);puts("");}
	#define FR first
	#define SE second
	#define MP make_pair
	#define pr pair<int,int>
	#define PB push_back
	#define vc vector
	void chmax(int &x,const int y) {x=x>y?x:y;}
	void chmin(int &x,const int y) {x=x<y?x:y;}
	const int MAX_N=2e5+10;
	const ll MOD=1e9+7;
	void add(int &x,int y){x+=y;if(x>=MOD) x-=MOD;if(x<0) x+=MOD;}
	
	struct BIT
	{
		vc<int> bit[MAX_N];int now[MAX_N];BIT(){memset(now,0,sizeof now);}
		#define lowbit(x) ((x)&-(x))
		void change(int x,int c){while(x<MAX_N) bit[x].PB(max(bit[x][now[x]],c)),now[x]++,x+=lowbit(x);}
		int ask(int x){int ans=-INF;while(x>=1) chmax(ans,bit[x][now[x]]),x-=lowbit(x);return ans;}
		void gaygay(int x){while(x<MAX_N) now[x]--,x+=lowbit(x);}
	}bit[2];
	int a[MAX_N];vc<int> ans;
	int c[2],mi[2],cnt[MAX_N];
	bool check(int i,int now)
	{
		int tmp1=c[now],tmp2=mi[now];
		if(a[i]<mi[now]) c[now]++,mi[now]=a[i];
		for(int j=0;j<=1;j++)
		{
			int wt=c[j]-c[j^1]+cnt[i+1];if(wt<0) continue;
			if(bit[wt&1].ask(mi[j^1])>=wt) return 1;
		}
		c[now]=tmp1;mi[now]=tmp2;
		return 0;
	}
	void main()
	{
		for(int i=1;i<MAX_N;i++) bit[0].bit[i].PB(0);
		for(int i=1;i<MAX_N;i++) bit[1].bit[i].PB(-1);
		
		int n=qread();for(int i=1;i<=n;i++) a[i]=n-qread()+1;
		int lstmi=INF;for(int i=1;i<=n;i++) if(a[i]<lstmi) lstmi=a[i],cnt[i]=1; else cnt[i]=0;
		for(int i=n;i>=1;i--) cnt[i]+=cnt[i+1];
		
		for(int i=n;i>=1;i--)
		{
			int t0=bit[0].ask(a[i]),t1=bit[1].ask(a[i]);if(t1==-1) t1=-INF;
			t0+=1+(cnt[i]-cnt[i+1]);t1+=1+(cnt[i]-cnt[i+1]);
			if((t0&1)==(t1&1)) bit[t1&1].change(a[i],max(t0,t1)),bit[(t1&1)^1].change(a[i],-INF);
			else bit[t0&1].change(a[i],t0),bit[t1&1].change(a[i],t1);
		}
		mi[0]=mi[1]=n+1;
		for(int i=1;i<=n;i++)
		{
			bit[0].gaygay(a[i]);bit[1].gaygay(a[i]);
			
			if(check(i,0)) ans.PB(0);
			else if(check(i,1)) ans.PB(1);
			else {puts("-1");return;}
		}
		for(int t=0;t<n;t++) putchar('0'+ans[t]);
	}
};
signed main()
{
	srand(time(0));
	mine::main();
}