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 <vector>
#include <cstring>
using namespace std;
const int N = 200064, inf = 0xcdcdcdcd;
inline void Max(int &a, int b) {if (a < b) a = b;}

int p[N], f[2][N], t[N], n;
bool h[N];
vector<pair<int*,int>> stk;

void upd(int (&tr)[N], int x, int v) {
	do if (tr[x] < v) {
		stk.emplace_back(tr+x, tr[x]);
		tr[x] = v;
	  }
	while (x &= x-1);
}
int qry(int (&tr)[N], int x) {
	int v = inf-8;
	do Max(v, tr[x]);
	while ((x += x&-x) <= n);
	return v;
}

inline bool chk(int h1, int d) {	// d = c0 - c1 + q;
	return d >= 0 && qry(f[d&1], h1) >= d;
}
inline bool check(int h0, int h1, int d, int q) {	// d = c0 - c1
	return chk(h0, q - d) || chk(h1, q + d);
}

int main() {
	scanf("%d",&n);
	memset(f[1]+1, 0xcc, n<<2);
	int q = 0;
	for (int i = 0, mx = 0; i < n; i++) {
		scanf("%d",p+i);
		if (p[i] > mx) {
			mx = p[i];
			h[i] = true;
			q++;
		}
	}
	for (int i = n, g0, g1; i--;) {
		t[i] = stk.size();
		if (h[i]) {	//w = 2
			g0 = qry(f[0], p[i]) + 2;
			g1 = qry(f[1], p[i]) + 2;
		} else {	//w = 1
			g0 = qry(f[1], p[i]) + 1;
			g1 = qry(f[0], p[i]) + 1;
		}
		if (g0 > inf) upd(f[0], p[i], g0);
		if (g1 > inf) upd(f[1], p[i], g1);
	}
	if (!chk(1, q)) {puts("-1"); return 0;}
	int h0 = 1, h1 = 1, d = 0, top = stk.size();
	for (int i = 0; i < n; i++) {
		q -= h[i];
		while (top > t[i]) {	//undo
			auto &p = stk[--top];
			*p.first = p.second;
		}
		if (h0 <= p[i])
			if (check(p[i], h1, d+1, q)) {
				putchar('0');
				h0 = p[i]; d++;
			} else {
				putchar('1');
				if (h1 <= p[i])
					h1 = p[i], d--;
			}
		else if (check(h0, h1, d, q))
				putchar('0');
			else {
				putchar('1');
				if (h1 <= p[i])
					h1 = p[i], d--;
			}
	}
	return 0;
}