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 <bits/stdc++.h>
using namespace std;
typedef bool boolean;

const int N = 2e5 + 5;

const int inf = (signed) (~0u >> 2);

typedef class SegTreeNode {
	public:
		int v;
		SegTreeNode *l, *r;
		
		SegTreeNode() : v(-inf), l(NULL), r(NULL) {	}

		void push_up() {
			v = max(l->v, r->v);
		}
} SegTreeNode;

SegTreeNode pool[N << 2];
SegTreeNode *_top = pool;

typedef class SegmentTree {
	public:
		int n;
		SegTreeNode* rt;

		void build(SegTreeNode*& p, int l, int r) {
			p = _top++;
			if (l == r) {
				return;
			}
			int mid = (l + r) >> 1;
			build(p->l, l, mid);
			build(p->r, mid + 1, r);
		}
		void build(int n) {
			this->n = n;
			build(rt, 1, n);
		}

		int query(SegTreeNode* p, int l, int r, int ql, int qr) {
			if (l == ql && r == qr) {
				return p->v;
			}
			int mid = (l + r) >> 1;
			if (qr <= mid) {
				return query(p->l, l, mid, ql, qr);
			} else if (ql > mid) {
				return query(p->r, mid + 1, r, ql, qr);
			}
			int a = query(p->l, l, mid, ql, mid);
			int b = query(p->r, mid + 1, r, mid + 1, qr);
			return max(a, b);
		}
		int query(int l, int r) {
			return query(rt, 1, n, l, r);
		}

		void modify(SegTreeNode* p, int l, int r, int idx, int v) {
			if (l == r) {
				p->v = v;
				return;
			}
			int mid = (l + r) >> 1;
			if (idx <= mid) {
				modify(p->l, l, mid, idx, v);
			} else {
				modify(p->r, mid + 1, r, idx, v);
			}
			p->push_up();
		}
		void modify(int idx, int v) {
			modify(rt, 1, n, idx, v);
		}
} SegmentTree;

int n;
int a[N];
int cnt[N];
int f[N][2];
char ans[N];
boolean isp[N];
SegmentTree st[2];

boolean check(int i, int mxX, int cntX, int mxY, int cntY) {
	// cntX + Q - k = cntY + k + m
	// 2k + m = cntX + Q - cntY
	int Q = cnt[n] - cnt[i];
	int dlt = cntX + Q - cntY;
	if (dlt >= 0 && st[dlt & 1].query(mxY + 1, n + 1) >= dlt)
		return true;
	dlt = cntY + Q - cntX;
	return dlt >= 0 && (st[dlt & 1].query(mxX + 1, n + 1) >= dlt);
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", a + i);
	}
	int mx = 0;
	for (int i = 1; i <= n; i++) {
		mx = max(mx, a[i]);
		isp[i] = (mx == a[i]);
		cnt[i] = cnt[i - 1] + isp[i];
	}
	st[0].build(n + 1);
	st[1].build(n + 1);
	f[n + 1][0] = 0;
	f[n + 1][1] = -inf;
	st[0].modify(n + 1, 0);
	for (int i = n; i; i--) {
		if (isp[i]) {
			f[i][0] = st[0].query(a[i], n + 1) + 2;
			f[i][1] = st[1].query(a[i], n + 1) + 2;
		} else {
			f[i][0] = st[1].query(a[i], n + 1) + 1;
			f[i][1] = st[0].query(a[i], n + 1) + 1;
		}
		st[0].modify(a[i], f[i][0]);
		st[1].modify(a[i], f[i][1]);
	}
//	for (int i = 1; i <= n; i++)
//		cerr << f[i][0] << " ";
//	cerr << '\n';
//	for (int i = 1; i <= n; i++)
//		cerr << f[i][1] << " ";
//	cerr << '\n';
	int cntX = 0, cntY = 0;
	int mxX = 0, mxY = 0;
	if (!check(0, 0, 0, 0, 0)) {
		puts("-1");
		return 0;
	}
	for (int i = 1; i <= n; i++) {
		st[0].modify(a[i], -inf);
		st[1].modify(a[i], -inf);
		if (check(i, max(a[i], mxX), cntX + (a[i] > mxX), mxY, cntY)) {
			ans[i] = '0';
			cntX += (a[i] > mxX);
			mxX = max(a[i], mxX);
		} else {
			ans[i] = '1';
			cntY += (a[i] > mxY);
			mxY = max(a[i], mxY);
		}
	}
	puts(ans + 1);
	return 0;
}