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 cs const
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;
typedef pair<int, int> pi;
cs int N = 2e5 + 50;
cs int INF = 1e9 + 7;
int n, a[N], c[N], bck[N][2];
struct bit{
	int c[N]; pi st[N<<5]; int top;
	void init(){ memset(c,-0x3f,sizeof(c)); }
	void mdf(int x, int v){ ++x; for(;x;x-=x&-x) st[++top]=mp(x,c[x]),c[x]=max(c[x],v); }
	int qry(int x){ int as=-INF; ++x; for(;x<=n+1;x+=x&-x) as=max(as,c[x]); return as; }
	void back(int bot){ while(top>bot) c[st[top].fi]=st[top].se, --top; }
}odd, even;
bool chk(int x, int v){
	if(v<0) return false;
	if(v&1) return odd.qry(x)>=v;
	return even.qry(x)>=v;
}
int main(){
	#ifdef FSYolanda
	freopen("1.in","r",stdin);
	#endif
	scanf("%d",&n);
	for(int i=1,mx=0; i<=n; i++){
		scanf("%d",&a[i]);
		if(a[i]>mx) c[i]=2; else c[i]=1;
		mx=max(mx,a[i]); 
	} odd.init(); for(int i=n; i>=1; i--){
		bck[i][0]=odd.top, bck[i][1]=even.top;
		int A=odd.qry(a[i]), B=even.qry(a[i]);
		if(c[i]&1) even.mdf(a[i],A+c[i]), odd.mdf(a[i],B+c[i]);
		else odd.mdf(a[i],A+c[i]), even.mdf(a[i],B+c[i]);
	} for(int i=n; i>=1; i--) c[i]+=c[i+1]-1;
	int cx=0, cy=0, mx=0, my=0;
	static bool ans[N];
	for(int i=1; i<=n; i++){
		odd.back(bck[i][0]); 
		even.back(bck[i][1]);
		if(chk(my,cx-cy+c[i+1]+(a[i]>mx))) 
		cx+=a[i]>mx, mx=max(mx,a[i]), ans[i]=0;
		else if(chk(max(mx,a[i]),cy+c[i+1]-cx-(a[i]>mx)))
		cx+=a[i]>mx, mx=max(mx,a[i]), ans[i]=0;
		else ans[i]=1, cy+=a[i]>my, my=max(my,a[i]);
	} if(cx^cy) return puts("-1"),0;
	for(int i=1; i<=n; i++) cout<<ans[i];
	return 0;
}