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>
#define ll long long
using namespace std;
template <typename T> void chkmax(T &x, T y) {x = x > y ? x : y;}
template <typename T> void chkmin(T &x, T y) {x = x > y ? y : x;}
template <typename T> void read(T &x) {
	x = 0; int f = 1; char c = getchar();
	while (!isdigit(c)) {if (c == '-') f = -1; c = getchar();}
	while (isdigit(c)) x = x * 10 + c - '0', c = getchar(); x *= f;
}
const int N = 200010;
int n, a[N], s[N], val[N];
struct SegmentTree {
	const static int M = N * 4;
	#define lc k << 1
	#define rc k << 1 | 1
	int mx[M];
	void modify(int k, int l, int r, int x, int v) {
		if (l == r) return mx[k] = v, void();
		int mid = (l + r) >> 1;
		if (x <= mid) modify(lc, l, mid, x, v);
			else modify(rc, mid + 1, r, x, v);
		mx[k] = max(mx[lc], mx[rc]);
	}
	int query(int k, int l, int r, int L, int R) {
		if (L <= l && r <= R) return mx[k];
		int mid = (l + r) >> 1, ret = -1e9;
		if (L <= mid) chkmax(ret, query(lc, l, mid, L, R));
		if (R > mid) chkmax(ret, query(rc, mid + 1, r, L, R));
		return ret;
	}
} T0, T1;
bool check(int mx, int s) {
	if (s < 0) return false;
	if (s & 1) return T1.query(1, 1, n, mx, n) >= s;
	return T0.query(1, 1, n, mx, n) >= s;
}
int main() {
	read(n);
	for (int i = 1, mx = 0; i <= n; i++) {
		read(a[i]), val[i] = 1 + (a[i] > mx);
		chkmax(mx, a[i]);
	}
	memset(T1.mx, -0x3f, sizeof(T1.mx));
	for (int i = n; i; i--) {
		int v0 = T0.query(1, 1, n, a[i], n), v1 = T1.query(1, 1, n, a[i], n);
		if (val[i] & 1) T0.modify(1, 1, n, a[i], v1 + val[i]), T1.modify(1, 1, n, a[i], v0 + val[i]);
			else T0.modify(1, 1, n, a[i], v0 + val[i]), T1.modify(1, 1, n, a[i], v1 + val[i]);
	}
	for (int i = n; i; i--) s[i] = s[i + 1] + val[i] - 1;
	int cntx = 0, cnty = 0, mxx = 0, mxy = 0; string st = "";
	for (int i = 1; i <= n; i++) {
		T0.modify(1, 1, n, a[i], 0), T1.modify(1, 1, n, a[i], 1 - 1e9);
		if (check(mxy, cntx + s[i + 1] - cnty + (a[i] > mxx))) st = st + '0', cntx += a[i] > mxx, chkmax(mxx, a[i]);
			else if (check(max(mxx, a[i]), cnty + s[i + 1] - cntx - (a[i] > mxx))) st = st + '0', cntx += a[i] > mxx, chkmax(mxx, a[i]);
				else st = st + '1', cnty += a[i] > mxy, chkmax(mxy, a[i]);
	}
	if (cntx != cnty) cout << "-1\n"; else cout << st << '\n';
	return 0;
}