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 <cstdio>
#include <algorithm>
#include <vector>

inline int read()
{
	int data = 0, w = 1; char ch = getchar();
	while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
	if (ch == '-') w = -1, ch = getchar();
	while (ch >= '0' && ch <= '9') data = data * 10 + (ch ^ 48), ch = getchar();
	return data * w;
}

const int N(2e5 + 10), INF(1e9);
int n, p[N], val[N], cnt[N]; char s[N];
struct
{
	int max[N << 2];
	void build(int x = 1, int l = 1, int r = n)
	{
		max[x] = -INF; if (l == r) return;
		int mid = (l + r) >> 1, ls = x << 1, rs = ls | 1;
		build(ls, l, mid), build(rs, mid + 1, r);
	}

	void Modify(int p, int v, int x = 1, int l = 1, int r = n)
	{
		if (l == r) return (void) (max[x] = v);
		int mid = (l + r) >> 1, ls = x << 1, rs = ls | 1;
		if (p <= mid) Modify(p, v, ls, l, mid);
		else Modify(p, v, rs, mid + 1, r);
		max[x] = std::max(max[ls], max[rs]);
	}

	int Max(int ql, int qr, int x = 1, int l = 1, int r = n)
	{
		if (ql <= l && r <= qr) return max[x];
		int mid = (l + r) >> 1, ls = x << 1, rs = ls | 1, ans = -INF;
		if (ql <= mid) ans = Max(ql, qr, ls, l, mid);
		if (mid < qr) ans = std::max(ans, Max(ql, qr, rs, mid + 1, r));
		return ans;
	}
} A, B;

int check(int x, int Q)
{
	if (Q < 0) return 0;
	if (Q & 1) return A.Max(x, n) >= Q;
	else return B.Max(x, n) >= Q;
}

int main()
{
	n = read(), A.build();
	for (int i = 1, mx = 0; i <= n; i++)
		if ((p[i] = read()) > mx) mx = p[i], val[i] = 2;
		else val[i] = 1;
	for (int i = n; i; i--)
	{
		int x = A.Max(p[i], n), y = B.Max(p[i], n);
		if (val[i] & 1) B.Modify(p[i], x + val[i]), A.Modify(p[i], y + val[i]);
		else A.Modify(p[i], x + val[i]), B.Modify(p[i], y + val[i]);
	}
	for (int i = n; i; i--) cnt[i] = cnt[i + 1] + (val[i] == 2);
	int cntx = 0, cnty = 0, mxx = 0, mxy = 0;
	for (int i = 1; i <= n; i++)
	{
		A.Modify(p[i], -INF), B.Modify(p[i], 0);
		if (check(mxy, cntx + (p[i] > mxx) + cnt[i + 1] - cnty)
		 || check(std::max(mxx, p[i]), cnty + cnt[i + 1] - cntx - (p[i] > mxx)))
			s[i] = '0', cntx += p[i] > mxx, mxx = std::max(mxx, p[i]);
		else s[i] = '1', cnty += p[i] > mxy, mxy = std::max(mxy, p[i]);
	}
	if (cntx != cnty) puts("-1"); else puts(s + 1);
	return 0;
}