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 <cmath>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 200100;
struct Node
{
	int mx[2];
	Node *lch, *rch;
	Node() : mx(), lch(0), rch(0) {}
}node[maxn * 41];
typedef Node *pnode;
int tot = 0;
pnode root[maxn];
void update(pnode r)
{
	r->mx[0] = max(r->lch->mx[0], r->rch->mx[0]);
	r->mx[1] = max(r->lch->mx[1], r->rch->mx[1]);
}
void build(pnode &r, int st, int ed)
{
	r = &node[++ tot];
	if(st == ed)
		return ;
	int mid = (st + ed) >> 1;
	build(r->lch, st, mid);
	build(r->rch, mid + 1, ed);
}
int ask(pnode r, int ll, int rr, int asd, int st, int ed)
{
	if(ll > rr)
		return 0;
	if(ll == st && rr == ed)
		return r->mx[asd];
	int ans = 0;
	int mid = (st + ed) >> 1;
	if(ll <= mid)
		ans = max(ans, ask(r->lch, ll, min(mid, rr), asd, st, mid));
	if(mid < rr)
		ans = max(ans, ask(r->rch, max(ll, mid + 1), rr, asd, mid + 1, ed));
	return ans;
}
void change(pnode &r, pnode nxt, int x, int y, int st, int ed)
{
	r = &node[++ tot];
	*r = *nxt;
	if(st == ed)
	{
		r->mx[y & 1] = max(r->mx[y & 1], y);
		return ;
	}
	int mid = (st + ed) >> 1;
	if(x <= mid)
	{
		r->lch = 0;
		change(r->lch, nxt->lch, x, y, st, mid);
	}
	else
	{
		r->rch = 0;
		change(r->rch, nxt->rch, x, y, mid + 1, ed);
	}
	update(r);
}
void out(pnode r, int st, int ed)
{
	cout << st << " " << ed << " " << r->mx[0] << " " << r->mx[1] << endl;
	if(st == ed)
		return ;
	int mid = (st + ed) >> 1;
	out(r->lch, st, mid);
	out(r->rch, mid + 1, ed);
}
int p[maxn], v[maxn], num[maxn];
int n;
int main()
{
	std::ios::sync_with_stdio(false);
	cin >> n;
	int mx = -1;
	num[0] = 0;
	for(int i = 1; i <= n; i ++)
	{
		cin >> p[i];
		if(p[i] > mx)
		{
			v[i] = 2;
			mx = p[i];
		}
		else
			v[i] = 1;
		num[i] = num[i - 1] + v[i] - 1;
	}
	build(root[n + 1], 1, n);
	for(int i = n; i >= 1; i --)
	{
		//cerr << i << " ---------------------- " << endl;
		int a = ask(root[i + 1], p[i] + 1, n, 0, 1, n);
		int b = ask(root[i + 1], p[i] + 1, n, 1, 1, n);
		//cout << a << " " << b << endl;
		//cout << a + v[i] << " " << b + v[i] << endl;
		change(root[i], root[i + 1], p[i], a + v[i], 1, n);
		change(root[i], root[i], p[i], b + v[i], 1, n);
		//out(root[i], 1, n);
	}
	string s = "";
	int c1 = 0, c2 = 0, mx1 = 0, mx2 = 0;
	//cout << num[n] << endl;
	//cout << ask(root[1], mx2 + 1, n, num[n] & 1, 1, n) << " " << ask(root[1], mx1 + 1, n, num[n] & 1, 1, n) << endl;
	if(ask(root[1], mx2 + 1, n, num[n] & 1, 1, n) < c1 - c2 + num[n] && ask(root[1], mx1 + 1, n, num[n] & 1, 1, n) < c2 - c1 + num[n])
	{
		cout << -1 << endl;
		return 0;
	}
	for(int i = 1; i <= n; i ++)
	{
		//cerr << i << " ----------- " << endl;
		int a = num[n] - num[i];
		int nxt1 = mx1, nxtc = c1;
		if(p[i] > mx1)
		{
			mx1 = p[i];
			c1 ++;
		}
		int asd = (c1 - c2 + a) & 1;
		//cout << c1 << " " << mx1 << " " << c2 << " " << mx2 << " " << a << " " << c1 - c2 + a << " " << asd << endl;
		//out(root[i + 1], 1, n);
		//cout << ask(root[i + 1], mx2 + 1, n, asd, 1, n) << " " << ask(root[i + 1], mx1 + 1, n, asd, 1, n) << endl;
		if((c1 - c2 + a >= 0 && ask(root[i + 1], mx2 + 1, n, asd, 1, n) >= c1 - c2 + a) || 
			(c2 - c1 + a >= 0 && ask(root[i + 1], mx1 + 1, n, asd, 1, n) >= c2 - c1 + a))
			s += '0';
		else
		{
			mx1 = nxt1;
			c1 = nxtc;
			if(p[i] > mx2)
			{
				mx2 = p[i];
				c2 ++;
			}
			s += '1';
		}
	}
	cout << s << endl;
	return 0;
}