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 <algorithm>
#include <cstring>
#include <cstdio>
#include <vector>
struct segT {
	int n, seg[200005];
	int val[4000005], idx[4000005], tp = 0;
	inline void modify(int pos, int x)
	{
		for (; pos <= n; pos += pos & -pos) {
			idx[tp] = pos;
			val[tp++] = seg[pos];
			seg[pos] = std::max(seg[pos], x);
		}
	}
	inline int query(int pos)
	{
		int res = -1e9;
		for (pos = std::min(pos, n); pos; pos -= pos & -pos) {
			res = std::max(res, seg[pos]);
		}
		return res;
	}
	inline void pop(int lim)
	{
		while (tp != lim) {
			tp--;
			seg[idx[tp]] = val[tp];
		}
	}
} seg[2];
char ans[200005];
int arr[200005], val[200005], enp[200005][2], suf[200005];
int main()
{
	// freopen("AGC028-E.in", "r", stdin);
	int n, cur_mn = 1e9;
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", arr + i);
		arr[i] = n - arr[i] + 1;
		val[i] = arr[i] < cur_mn;
		if (arr[i] < cur_mn) {
			cur_mn = arr[i];
		}
	}
	seg[0].n = seg[1].n = n;
	memset(seg[0].seg, 0, sizeof(seg[0].seg));
	memset(seg[1].seg, -0x3f, sizeof(seg[1].seg));
	for (int i = n - 1; i >= 0; i--) {
		suf[i] = suf[i + 1] + val[i];
		int tmp[2];
		for (int j = 0; j < 2; j++) {
			enp[i][j] = seg[j].tp;
			tmp[j] = std::max(0, seg[j].query(arr[i]));
		}
		for (int j = 0; j < 2; j++) {
			int x = tmp[j] + val[i] + 1;
			seg[x & 1].modify(arr[i], x);
		}
	}
	std::vector<int> cur = {n + 1, n + 1}, len = {0, 0};
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 2; j++) {
			seg[j].pop(enp[i][j]);
		}
		for (int j = 0; j < 2; j++) {
			auto ncur = cur, nlen = len;
			if (arr[i] < ncur[j]) {
				ncur[j] = arr[i];
				nlen[j]++;
			}
			bool flg = false;
			if (i + 1 == n) {
				flg = nlen[0] == nlen[1];
			} else {
				for (int k = 0; k < 2; k++) {
					int x = nlen[k] - nlen[k ^ 1] + suf[i + 1];
					if (x >= 0 && seg[x & 1].query(ncur[k ^ 1]) >= x) {
						flg = true;
					}
				}
			}
			if (flg) {
				ans[i] = j + '0';
				cur = ncur;
				len = nlen;
				break;
			}
		}
		if (!ans[i]) {
			puts("-1");
			return 0;
		}
	}
	puts(ans);
	return 0;
}