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:
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define jizz ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define pb push_back
#define MP make_pair
#define F first
#define S second
#define ET cout << "\n"
#define MEM(i,j) memset(i,j,sizeof i)
#define ALL(v) v.begin(),v.end()
#define DB(a,s,e) {for(int i=s;i<e;++i) cerr << a[i] << " ";ET;}
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

int arr[200005],seg[2][800005];
bitset<200005> high;
string ans;

void modify(int x,int l,int r,int rt,int t,int v)
{
	if(l==r)
		return seg[t][rt]=v,void();
	int m=l+r>>1;
	if(x<=m) modify(x,l,m,rt<<1,t,v);
	else modify(x,m+1,r,rt<<1|1,t,v);
	seg[t][rt]=max(seg[t][rt<<1],seg[t][rt<<1|1]);
}

int query(int L,int R,int l,int r,int rt,int t)
{
	if(L<=l&&R>=r) return seg[t][rt];
	int m=l+r>>1;
	if(R<=m) return query(L,R,l,m,rt<<1,t);
	if(L>m) return query(L,R,m+1,r,rt<<1|1,t);
	return max(query(L,R,l,m,rt<<1,t),query(L,R,m+1,r,rt<<1|1,t));
}

int main()
{jizz
	int n,mx=0,a,b,ma,mb,cnt;
	cin >> n;
	for(int i=1;i<=n;++i)
		cin >> arr[i],high[i]=(arr[i]>mx),mx=max(mx,arr[i]);
	for(int i=n;i>=1;--i)
	{
		a=query(arr[i]+1,n+1,1,n+1,1,0)+high[i]+1,b=query(arr[i]+1,n+1,1,n+1,1,1);
		if(b&1) b+=high[i]+1,modify(arr[i],1,n+1,1,b&1,b);
		modify(arr[i],1,n+1,1,a&1,a);
	}
	cnt=high.count();
	if(seg[cnt&1][1]<cnt)
		return cout << "-1\n",0;
	a=b=ma=mb=0;
	for(int i=1;i<=n;++i)
	{
		modify(arr[i],1,n+1,1,0,0),modify(arr[i],1,n+1,1,1,0);
		cnt-=high[i];
		int t=a-b+cnt+(arr[i]>ma);
		if(t>=0&&query(mb+1,n+1,1,n+1,1,t&1)>=t)
			a+=(arr[i]>ma),ma=max(ma,arr[i]),ans.pb('0');
		else if(t=b-a+cnt-(arr[i]>ma),t>=0&&query(max(ma,arr[i])+1,n+1,1,n+1,1,t&1)>=t)
			a+=(arr[i]>ma),ma=max(ma,arr[i]),ans.pb('0');
		else
			b+=(arr[i]>mb),mb=max(mb,arr[i]),ans.pb('1');
	}
	cout << ans << "\n";
}