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>
#define rep(i, a, b) for (int i = (a); i <= int(b); i++)
#define per(i, a, b) for (int i = (a); i >= int(b); i--)
#define fir first
#define sec second
#define tct template<class type>
using namespace std;

typedef long long ll;
typedef pair<int, int> P;
const int maxn = 2e5, maxm = 1 << 19, mod = 1e9 + 7;
int n, p[maxn + 5], a[maxn + 5], cnt[maxn + 5];
char s[maxn + 5];

inline void red(int &x) { x += x >> 31 & mod; }
tct inline void cmax(type &x, type y) { x < y ? x = y : 0; }
tct inline void cmin(type &x, type y) { x > y ? x = y : 0; }

struct tree {
	int mx[maxm + 5];
	#define ls (x << 1)
	#define rs (ls | 1)
	#define mid ((l + r) >> 1)
	void upd(int x) {
		mx[x] = max(mx[ls], mx[rs]);
	}
	void build(int x, int l, int r) {
		mx[x] = -1e9;
		if (l == r) return;
		build(ls, l, mid), build(rs, mid + 1, r);
	}
	void modify(int x, int l, int r, int y, int z) {
		if (l == r) return mx[x] = z, void();
		y <= mid ? modify(ls, l, mid, y, z) : modify(rs, mid + 1, r, y, z);
		upd(x);
	}
	int query(int x, int l, int r, int lx, int rx) {
		if (l >= lx && r <= rx) return mx[x];
		int y = -1e9;
		if (lx <= mid) cmax(y, query(ls, l, mid, lx, rx));
		if (rx > mid) cmax(y, query(rs, mid + 1, r, lx, rx));
		return y;
	}
} odd, eve;

bool check(int x, int y) {
	if (y < 0) return false;
	if (y & 1) return odd.query(1, 1, n, x, n) >= y;
	return eve.query(1, 1, n, x, n) >= y;
}

int main() {
	scanf("%d", &n);
	for (int i = 1, x = 0; i <= n; i++) {
		scanf("%d", &p[i]);
		if (x < p[i]) a[i] = 1, x = p[i];
	}
	odd.build(1, 1, n);
	per(i, n, 1) {
		int x = odd.query(1, 1, n, p[i], n), y = eve.query(1, 1, n, p[i], n);
		if (a[i]) odd.modify(1, 1, n, p[i], x + 2), eve.modify(1, 1, n, p[i], y + 2);
		else odd.modify(1, 1, n, p[i], y + 1), eve.modify(1, 1, n, p[i], x + 1);
	}
	per(i, n, 1) cnt[i] = cnt[i + 1] + a[i];
	int xc = 0, yc = 0, xm = 0, ym = 0;
	rep(i, 1, n) {
		odd.modify(1, 1, n, p[i], -1e9), eve.modify(1, 1, n, p[i], 0);
		int nxc = xc + (p[i] > xm);
		if (check(ym, nxc + cnt[i + 1] - yc) || check(max(xm, p[i]), yc + cnt[i + 1] - nxc)) {
			s[i] = '0', xc += p[i] > xm, xm = max(xm, p[i]);
		} else {
			s[i] = '1', yc += p[i] > ym, ym = max(ym, p[i]);
		}
	}
	if (xc != yc) puts("-1"), exit(0);
	puts(s + 1);
	return 0;
}