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>
#define pb push_back
struct BIT
{
	int n, seg[200005], idx[4000005], orig[4000005], cnt;
	inline void init(int _n, int val = -0x3f)
	{
		n = _n;
		cnt = 0;
		memset(seg, val, n + 1 << 2);
	}
	inline void modify(int pos, int val)
	{
		for (; pos <= n; pos += pos & -pos)
		{
			idx[cnt] = pos;
			orig[cnt++] = seg[pos];
			seg[pos] = std::max(seg[pos], val);
		}
	}
	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 reset(int sz)
	{
		while (cnt > sz)
		{
			cnt--;
			seg[idx[cnt]] = orig[cnt];
		}
	}
} seg[2];
int arr[200005], suf[200005], val[200005], pos[200005][2];
int mn[2], len[2], nxt_mn[2], nxt_len[2], res[2];
char ans[200005];
int main()
{
	// freopen("AGC028-E.in", "r", stdin);
	// freopen("AGC028-E.out", "wt", stdout);
	int n, cur = 1e9;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", arr + i);
		arr[i] = n - arr[i] + 1;
		if (arr[i] < cur)
		{
			cur = arr[i];
			val[i] = 2;
		}
		else
			val[i] = 1;
	}
	seg[0].init(n, 0);
	seg[1].init(n);
	for (int i = n - 1; i >= 0; i--)
		suf[i] = suf[i + 1] + (val[i] == 2);
	for (int i = n - 1; i >= 0; i--)
	{
		for (int j = 0; j < 2; j++)
			res[j] = std::max(0, seg[j].query(arr[i]));
		for (int j = 0; j < 2; j++)
		{
			int x = res[j] + val[i] & 1;
			seg[x].modify(arr[i], res[j] + val[i]);
		}
		for (int j = 0; j < 2; j++)
			pos[i][j] = seg[j].cnt;
	}
	mn[0] = mn[1] = 1e9;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < 2; j++)
			seg[j].reset(pos[i + 1][j]);
		for (int j = 0; j < 2; j++)
		{
			memcpy(nxt_len, len, sizeof(len));
			memcpy(nxt_mn, mn, sizeof(mn));
			if (arr[i] < nxt_mn[j])
			{
				nxt_mn[j] = arr[i];
				nxt_len[j]++;
			}
			bool flg = false;
			if (i == n - 1)
				flg = nxt_len[0] == nxt_len[1];
			else
			{
				for (int k = 0; k < 2; k++)
				{
					int need = nxt_len[k] - nxt_len[k ^ 1] + suf[i + 1];
					if (need >= 0 && need <= seg[need & 1].query(nxt_mn[k ^ 1]))
						flg = true;
				}
			}
			if (flg)
			{
				ans[i] = j + '0';
				memcpy(mn, nxt_mn, sizeof(mn));
				memcpy(len, nxt_len, sizeof(len));
				break;
			}
		}
		if (!ans[i])
		{
			puts("-1");
			return 0;
		}
	}
	puts(ans);
	return 0;
}