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 mset(a, b) memset(a, b, sizeof(a))
#define mcpy(a, b) memcpy(a, b, sizeof(a))
#define lc (rt << 1)
#define rc (rt << 1) | 1
using namespace std;
typedef long long LL;
const int MAXN = 200005;
const int INF = 0x3f3f3f3f;

template <typename T> inline void read(T &AKNOI) {
	T x = 0, flag = 1;
	char ch = getchar();
	while (!isdigit(ch)) {
		if (ch == '-') flag = -1;
		ch = getchar();
	}
	while (isdigit(ch)) {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	AKNOI = flag * x;
}

int n, a[MAXN], mx[MAXN];

struct SegmentTree {
	int seg[MAXN << 2];
	
	void Update(int rt, int b, int e, int p, int v) {
		if (b == e) {
			seg[rt] = v;
			return;
		}
		int mid = (b + e) >> 1;
		if (p <= mid) Update(lc, b, mid, p, v);
		else Update(rc, mid + 1, e, p, v);
		seg[rt] = max(seg[lc], seg[rc]);
	}
	
	int Query(int rt, int b, int e, int l, int r) {
		if (l <= b && e <= r) return seg[rt];
		int mid = (b + e) >> 1;
		if (r <= mid) return Query(lc, b, mid, l, r);
		if (l > mid) return Query(rc, mid + 1, e, l, r);
		return max(Query(lc, b, mid, l, r), Query(rc, mid + 1, e, l, r));
	}
} T1, T2;

bool Try(int p, int m1, int m2, int c1, int c2) {
	int need = c1 + mx[p] - c2;
	if (need >= 0 && (need & 1? T1 : T2).Query(1, 1, n, m2, n) >= need) return 1;
	need = c2 + mx[p] - c1;
	if (need >= 0 && (need & 1? T1 : T2).Query(1, 1, n, m1, n) >= need) return 1;
	return 0;
}

void init() {
	read(n);
	for (int i = 1, b = 0; i <= n; ++i) {
		read(a[i]);
		if (a[i] > b) mx[i] = 1;
		b = max(b, a[i]);
	}
	for (int i = n; i >= 1; --i) {
		mx[i] += mx[i + 1];
	}
}

void solve() {
	mset(T1.seg, 0x80);
	for (int i = n; i >= 1; --i) {
		int v1 = T1.Query(1, 1, n, a[i], n);
		int v2 = T2.Query(1, 1, n, a[i], n);
		T1.Update(1, 1, n, a[i], (mx[i] > mx[i + 1]? v1 + 2 : v2 + 1));
		T2.Update(1, 1, n, a[i], (mx[i] > mx[i + 1]? v2 + 2 : v1 + 1));
	}
	int m1 = 1, m2 = 1, c1 = 0, c2 = 0;
	string ans;
	for (int i = 1; i <= n; ++i) {
		T1.Update(1, 1, n, a[i], -INF);
		T2.Update(1, 1, n, a[i], 0);
		if (Try(i + 1, max(m1, a[i]), m2, c1 + (a[i] >= m1), c2)) {
			ans += '0';
			c1 += (a[i] >= m1);
			m1 = max(m1, a[i]);
		} else {
			ans += '1';
			c2 += (a[i] >= m2);
			m2 = max(m2, a[i]);
		}
	}
	if (c1 == c2) cout << ans << endl;
	else puts("-1");
}

int main() {
	init();
	solve();
	return 0;
}