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 target("tune=native")
#include <bits/stdc++.h>
using namespace std;

const int N = 200005;
int n, m, p[N], val[N], T[2][N * 3];
char ans[N];

void modify(int *T, int p, int v) {
	for (T[p += m] = v; p >>= 1;) {
		int w = max(T[p << 1], T[p << 1 | 1]);
		if (w == T[p]) break;
		T[p] = w;
	}
}
int query(int *T, int s) {
	int res = -(2 * N);
	for (s += m; s >>= __builtin_ctz(~s); s >>= 1) res = max(res, T[s ^ 1]);
	return res;
}

bool check(int x, int y) {
	return x >= 0 && x <= query(T[x & 1], y);
}

int main() {
	scanf("%d", &n);
	m = 1;
	while (m <= n) m <<= 1;
	for (int i = 1; i <= m + n + 1; ++i) T[1][i] = -(2 * N);
	int Q = 0, mx = 0;
	for (int i = 1; i <= n; ++i) {
		scanf("%d", p + i);
		if (p[i] > mx) mx = p[i], val[i] = 2, ++Q;
		else val[i] = 1;
	}
	for (int i = n; i; --i) {
		int tmp[2];
		for (int j = 0; j < 2; ++j) {
			tmp[j] = query(T[j ^ val[i] & 1], p[i]) + val[i];
			if (tmp[j] < 0) tmp[j] = -(2 * N);
		}
		for (int j = 0; j < 2; ++j) modify(T[j], p[i], tmp[j]);
	}
	if (!check(Q, 0)) return puts("-1"), 0;
	int c[2] = {}, h[2] = {};
	for (int i = 1; i <= n; ++i) {
		modify(T[0], p[i], 0), modify(T[1], p[i], -(2 * N));
		Q -= val[i] - 1;
		ans[i] = !(check(Q + c[1] - (c[0] + (p[i] > h[0])), max(h[0], p[i])) || check(Q - c[1] + (c[0] + (p[i] > h[0])), h[1]));
		if (p[i] > h[ans[i]]) ++c[ans[i]], h[ans[i]] = p[i];
		ans[i] += '0';
	}
	puts(ans + 1);
	return 0;
}