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 ll long long
using namespace std;
template<typename tn> void read(tn &a){
	tn x=0,f=1; char c=' ';
	for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
	for(;isdigit(c);c=getchar()) x=x*10+c-'0';
	a=x*f;
}
const int N = 301000;
int n,p[N],val[N],sum,f[N][2];
struct BIT{
	stack<int> c[N];
	void modify(int x,int k){
		for(int i=x;i;i-=i&-i) if(c[i].empty()||c[i].top()<=k) c[i].push(k);
	}
	void erase(int x,int k){
		for(int i=x;i;i-=i&-i) if(!c[i].empty()&&c[i].top()==k) c[i].pop();
	}
	int query(int x){
		int ans=-1e9;
		for(int i=x;i<=n;i+=i&-i) if(!c[i].empty()) ans=max(ans,c[i].top());
		return ans;
	}
}t[2];
bool check(int cnta,int cntb,int mxa,int mxb){
	int tmp=t[sum+cnta-cntb&1].query(mxb+1);
	if(tmp>=sum+cnta-cntb&&sum+cnta-cntb>=0) return 1;
	tmp=t[sum-cnta+cntb&1].query(mxa+1);
	if(tmp>=sum-cnta+cntb&&sum-cnta+cntb>=0) return 1;
	return 0;
}
int main(){
	read(n);
	for(int i=1;i<=n;i++)
		read(p[i]);
	int mx=0;
	for(int i=1;i<=n;i++)
		val[i]=p[i]>mx,mx=max(p[i],mx),sum+=val[i];
	t[0].modify(n,0);
	for(int i=n;i;i--){
		f[i][0]=t[0].query(p[i])+val[i]+1;
		f[i][1]=t[1].query(p[i])+val[i]+1;
		t[val[i]^1].modify(p[i],f[i][0]);
		t[val[i]].modify(p[i],f[i][1]);
	}
	int cnta=0,cntb=0,mxa=0,mxb=0;
	if(!check(0,0,0,0)){puts("-1");return 0;}
	for(int i=1;i<=n;i++){
		t[val[i]^1].erase(p[i],f[i][0]);
		t[val[i]].erase(p[i],f[i][1]);
		sum-=val[i];
		if(check(cnta+(p[i]>mxa),cntb,max(mxa,p[i]),mxb)){
			putchar('0');
			cnta+=p[i]>mxa;
			mxa=max(mxa,p[i]);
		}
		else{
			putchar('1');
			cntb+=p[i]>mxb;
			mxb=max(mxb,p[i]);
		}
	}
	puts("");
	return 0;
}