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>
using namespace std;

inline int gi()
{
	char c = getchar();
	while (c < '0' || c > '9') c = getchar();
	int sum = 0;
	while ('0' <= c && c <= '9') sum = sum * 10 + c - 48, c = getchar();
	return sum;
}

const int maxn = 200005;

int n, a[maxn], pmax[maxn], suf[maxn], res[maxn];
int len[2], p[2][maxn], Pmax[2][maxn], sum[2];

int rt[2][maxn], lch[maxn * 60], rch[maxn * 60], Max[maxn * 60], tot;

#define mid ((l + r) >> 1)

void insert(int &s, int l, int r, int p, int v)
{
	++tot;
	lch[tot] = lch[s]; rch[tot] = rch[s]; Max[tot] = Max[s];
	s = tot;
	if (l == r) return Max[s] = v, void();
	if (p <= mid) insert(lch[s], l, mid, p, v);
	else insert(rch[s], mid + 1, r, p, v);
	Max[s] = max(Max[lch[s]], Max[rch[s]]);
}

int query(int s, int l, int r, int ql, int qr)
{
	if (ql <= l && r <= qr) return Max[s];
	int res = 0;
	if (ql <= mid) res = max(res, query(lch[s], l, mid, ql, qr));
	if (qr >= mid + 1) res = max(res, query(rch[s], mid + 1, r, ql, qr));
	return res;
}

inline int check(int Id, int pos)
{
	int tmp = sum[Id] - sum[Id ^ 1] + suf[pos];
	if (tmp < 0) return 0;
	int res = query(rt[tmp & 1][pos], 1, n, Pmax[Id ^ 1][len[Id ^ 1]] + 1, n);
	return res >= tmp;
}

int main()
{	
	n = gi();
	for (int i = 1; i <= n; ++i) a[i] = gi(), pmax[i] = max(pmax[i - 1], a[i]);
	for (int i = n; i >= 1; --i) suf[i] = suf[i + 1] + (pmax[i] == a[i]);

	for (int i = n; i >= 1; --i) {
		int g0 = query(rt[0][i + 1], 1, n, a[i] + 1, n), g1 = query(rt[1][i + 1], 1, n, a[i] + 1, n);
		//printf("%d %d\n", g0, g1);
		if (pmax[i] == a[i]) {
			insert(rt[0][i] = rt[0][i + 1], 1, n, a[i], g0 + 2);
			if (g1) insert(rt[1][i] = rt[1][i + 1], 1, n, a[i], g1 + 2); else rt[1][i] = rt[1][i + 1];
		} else {
			insert(rt[1][i] = rt[1][i + 1], 1, n, a[i], g0 + 1);
			if (g1) insert(rt[0][i] = rt[0][i + 1], 1, n, a[i], g1 + 1); else rt[0][i] = rt[0][i + 1];
		}
	}

	fill(res + 1, res + n + 1, -1);
	for (int i = 1; i <= n; ++i) {
		for (int d = 0; d < 2; ++d) {
			p[d][++len[d]] = a[i];
			Pmax[d][len[d]] = max(Pmax[d][len[d] - 1], a[i]);
			sum[d] += Pmax[d][len[d]] == p[d][len[d]];

			if (check(0, i + 1)) {res[i] = d; break;}
			if (check(1, i + 1)) {res[i] = d; break;}

			sum[d] -= Pmax[d][len[d]] == p[d][len[d]];
			--len[d];
		}
		if (!~res[i]) return puts("-1"), 0;
	}

	for (int i = 1; i <= n; ++i) printf("%d", res[i]);
	
	return 0;
}