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 <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std;
inline int read()
{
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9') {if(ch == '-') f = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9') {x = (x << 3) + (x << 1) + (ch ^ 48); ch = getchar();}
	return x * f;
}
const int N = 1e6 + 1100,inf = 1e9;
int n,mx,a[N],val[N],sum[N];
char s[N];
struct node
{
	int tr[N << 2];
	void build(int k,int l,int r)
	{
		if(l == r) {tr[k] = -inf; return;}
		int mid = (l + r) >> 1;
		build(k << 1,l,mid); build(k << 1 | 1,mid + 1,r);
		tr[k] = max(tr[k << 1],tr[k << 1 | 1]);
	}
	void change(int k,int l,int r,int pos,int v)
	{
		if(l == r) {tr[k] = v; return;}
		int mid = (l + r) >> 1;
		if(pos <= mid) change(k << 1,l,mid,pos,v);
		else change(k << 1 | 1,mid + 1,r,pos,v);
		tr[k] = max(tr[k << 1],tr[k << 1 | 1]);
	}
	int ask(int k,int l,int r,int x,int y)
	{
		if(x <= l && y >= r) return tr[k];
		int mid = (l + r) >> 1,res = -inf;
		if(x <= mid) res = max(res,ask(k << 1,l,mid,x,y));
		if(y > mid)  res = max(res,ask(k << 1 | 1,mid + 1,r,x,y));
		return res;
	}
}Odd,Even;
int check(int mx,int Q)
{
	if(Q < 0) return 0;
	if(Q & 1) return Odd.ask(1,1,n,mx,n) >= Q;
	return Even.ask(1,1,n,mx,n) >= Q;
}
int main()
{
	n = read();
	for(int i = 1;i <= n;i ++)
	{
		a[i] = read();
		if(mx < a[i]) val[i] = 2,mx = a[i];
		else val[i] = 1;
	}
	Odd.build(1,1,n);
	for(int i = n,mx0,mx1;i >= 1;i --)
	{
		mx1 = Odd.ask(1,1,n,a[i],n); mx0 = Even.ask(1,1,n,a[i],n);
		if(val[i] & 1) Odd.change(1,1,n,a[i],mx0 + val[i]),Even.change(1,1,n,a[i],mx1 + val[i]);
		else Odd.change(1,1,n,a[i],mx1 + val[i]),Even.change(1,1,n,a[i],mx0 + val[i]);
	}
	for(int i = n;i >= 1;i --) sum[i] = sum[i + 1] + val[i] - 1;
	int cntx = 0,cnty = 0,mxx = 0,mxy = 0;
	for(int i = 1;i <= n;i ++)
	{
		Odd.change(1,1,n,a[i],-inf); Even.change(1,1,n,a[i],0);
		if(check(mxy,cntx + sum[i + 1] - cnty + (a[i] > mxx))) s[i] = '0',cntx += a[i] > mxx,mxx = max(mxx,a[i]);
		else if(check(max(mxx,a[i]),cnty + sum[i + 1] - cntx - (a[i] > mxx))) s[i] = '0',cntx += a[i] > mxx,mxx = max(mxx,a[i]);
		else s[i] = '1',cnty += a[i] > mxy,mxy = max(mxy,a[i]);
	}
	if(cntx != cnty) cout << "-1";
	else printf("%s",s + 1);
	fclose(stdin); fclose(stdout);
	return 0;
}