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>

const int N = 200000 + 7, T = N * 100;

int n;
int a[N], b[N], d[N];

int rt[N][2];
int kid[T][2], dat[T], ct;
void insert(int& p, int lp, int l, int r, int x, int y) {
	dat[p = ++ct] = dat[lp];
	kid[p][0] = kid[lp][0];
	kid[p][1] = kid[lp][1];
	if (l == r)
		dat[p] = std::max(dat[p], y);
	else {
		int m = l + r >> 1;
		if (x <= m) insert(kid[p][0], kid[lp][0], l, m, x, y);
		else insert(kid[p][1], kid[lp][1], m + 1, r, x, y);
		dat[p] = std::max(dat[kid[p][0]], dat[kid[p][1]]);
	}
}
int get(int p, int l, int r, int x, int y) {
	if (x > y) return -(1 << 28);
	if (x <= l && r <= y) return dat[p];
	int m = l + r >> 1, t = -(1 << 28);
	if (x <= m) t = std::max(t, get(kid[p][0], l, m, x, y));
	if (y > m) t = std::max(t, get(kid[p][1], m + 1, r, x, y));
	return t;
}

int f0, f1, g0, g1;
int ok(int m) {
	int f;
	f = f1 - f0 + d[m + 1];
	if (0 <= f && f <= get(rt[m + 1][f & 1], 1, n, g0 + 1, n)) return 1;
	f = f0 - f1 + d[m + 1];
	if (0 <= f && f <= get(rt[m + 1][f & 1], 1, n, g1 + 1, n)) return 1;
	return 0;
}

int s[N];

int main() {
//	freopen("code.in", "r", stdin);
//	freopen("code.out", "w", stdout);

	scanf("%d", &n);
	for (int i = 1; i <= n; ++i)
		scanf("%d", a + i), b[i] = std::max(a[i], b[i - 1]);
	for (int i = n; i; --i) {
		d[i] = d[i + 1] + (a[i] == b[i]);
		int f0 = std::max(0, get(rt[i + 1][0], 1, n, a[i] + 1, n)) + 1 + (a[i] == b[i]);
		int f1 = std::max(0, get(rt[i + 1][1], 1, n, a[i] + 1, n)) + 1 + (a[i] == b[i]);
		rt[i][0] = rt[i + 1][0], rt[i][1] = rt[i + 1][1];
		insert(rt[i][f0 & 1], rt[i][f0 & 1], 1, n, a[i], f0);
		insert(rt[i][f1 & 1], rt[i][f1 & 1], 1, n, a[i], f1);
	}

	f0 = 1, g0 = a[1];
	for (int i = 2; i <= n; ++i) {
		int lg0 = g0;
		if (a[i] > g0) g0 = a[i], ++f0;
		if (s[i] = !ok(i)) {
			if (a[i] > lg0) g0 = lg0, --f0;
			if (a[i] > g1) g1 = a[i], ++f1;
		}
	}
	if (f0 != f1)
		printf("-1");
	else
		for (int i = 1; i <= n; ++i) printf("%d", s[i]);
	return 0;
}