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 <iostream>
#include <cstdio>
#define MN 201000

int n, a[MN];
bool ok[MN]; int s[MN], f[MN];
int Max[MN * 20], ls[MN * 20], rs[MN * 20], tot = 0;
int rt[MN];

int modify(int x, int l, int r, int k, int v)
{
	int o = ++tot;
	ls[o] = ls[x]; rs[o] = rs[x];
	Max[o] = std::max(Max[x], v);
	if(l == r) return o;
	int mid = l + r >> 1;
	if(k <= mid) ls[o] = modify(ls[x], l, mid, k, v);
	else rs[o] = modify(rs[x], mid + 1, r, k, v);
	return o;
}

int query(int x, int l, int r, int L, int R)
{
	if(l == L && r == R) return Max[x];
	int mid = l + r >> 1;
	if(R <= mid) return query(ls[x], l, mid, L, R);
	else if(L > mid) return query(rs[x], mid + 1, r, L, R);
	else return std::max(query(ls[x], l, mid, L, mid), query(rs[x], mid + 1, r, mid + 1, R));
}

int Abs(int x) {return x > 0 ? x : -x;}

bool check(int len0, int len1, int now0, int now1, int i)
{
	if(Abs(len0 - len1) <= s[i] && ((len0 - len1) & 1) == (s[i] & 1)) return 1;
	if(len0 - len1 <= s[i] && len1 - len0 <= query(rt[i], 1, n, now0, n) - s[i]) return 1;
	if(len1 - len0 <= s[i] && len0 - len1 <= query(rt[i], 1, n, now1, n) - s[i]) return 1;
	return 0;
}

int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
	int now = 0;
	for(int i = 1; i <= n; i++)
	{
		if(a[i] > now) ok[i] = 1;
		now = std::max(now, a[i]);
	}
	for(int i = n; i >= 1; i--)
	{
		s[i] = s[i + 1] + ok[i];
		int g = query(rt[i + 1], 1, n, a[i], n);
		if(!ok[i]) f[i] = std::max(2 * s[i], g) + 1;
		else if(g) f[i] = g + 2;
		rt[i] = modify(rt[i + 1], 1, n, a[i], f[i]);
	}
	int len0 = 0, len1 = 0, now0 = 1, now1 = 1;
	if(!check(0, 0, 1, 1, 1)) return 0 * puts("-1");
	for(int i = 1; i <= n; i++)
	{
		if(check(len0 + (a[i] >= now0), len1, std::max(now0, a[i]), now1, i + 1))
		{
			printf("0");
			len0 += (a[i] >= now0);
			now0 = std::max(now0, a[i]);
		}
		else
		{
			printf("1");
			len1 += (a[i] >= now1);
			now1 = std::max(now1, a[i]);
		}
	}
}