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;
const int maxn = 2e5, inf = 1e8;
int n, p[maxn + 10], val[maxn + 10];
int f[maxn + 10][2], suf[maxn + 10];
vector<int> a, b, ans;

struct bit {
	int c[maxn + 10], w[maxn + 10];
	vector<pair<int, int> > mod[maxn + 10];
	
	void sss() {
		memcpy(w, c, sizeof c);
	}
	
	void xxx() {
		memcpy(c, w, sizeof w);
	}

	void init(int v) {
		for (int i = 1; i <= n + 1; ++i) c[i] = v;
	}

	void modify(int p, int v, int id) {
		p = n + 1 - p;
		for (; p <= n + 1; p += p & -p) {
			mod[id].push_back(make_pair(p, c[p]));
			c[p] = max(c[p], v);
		}
	}

	int query(int p) {
		p = n + 1 - p;
		int ans = -inf;
		for (; p; p -= p & -p) ans = max(ans, c[p]);
		return ans;
	}
	
	void undo(int id) {
		for (auto i: mod[id])
			c[i.first] = i.second;
	}

}c[2];

bool push(vector<int> &a, int v) {
	if (a.empty() || v > a.back()) {
		a.push_back(v); return 1;
	}
	return 0;
}

bool chk(int id) {
	int v = (int)b.size() + suf[id + 1] - (int)a.size();
	return v >= 0 && c[v & 1].query(a.empty() ? 0 : a.back()) >= v;
}

vector<int> solve1() {
	c[0].xxx(); c[1].xxx();
	a.clear(); b.clear();
	vector<int> ans;
	for (int i = 1; i <= n; ++i) {
		c[0].undo(i); c[1].undo(i);
		bool is = push(a, p[i]);
		if (chk(i)) ans.push_back(0);
		else {
			ans.push_back(1);
			if (is) a.pop_back();
			push(b, p[i]);
			if (!chk(i)) {
				ans.clear(); ans.push_back(inf);
				return ans;
			}
		}
	}
	return ans;
}

vector<int> solve2() {
	c[0].xxx(); c[1].xxx();
	a.clear(); b.clear();
	vector<int> ans;
	for (int i = 1; i <= n; ++i) {
		c[0].undo(i); c[1].undo(i);
		bool is = push(b, p[i]);
		if (chk(i)) ans.push_back(0);
		else {
			ans.push_back(1);
			if (is) b.pop_back();
			push(a, p[i]);
			if (!chk(i)) {
				ans.clear(); ans.push_back(inf);
				return ans;
			}
		}
	}
	return ans;
}


int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) scanf("%d", &p[i]);
	for (int i = 1; i <= n; ++i)
		if (push(a, p[i])) val[i] = 2;
		else val[i] = 1;
	c[0].init(0); c[1].init(-inf);
	for (int i = 1; i <= n; ++i) f[i][0] = f[i][1] = -inf;
	for (int i = n; i >= 1; --i) {
		f[i][val[i] & 1] = c[0].query(p[i]) + val[i];
		f[i][(val[i] ^ 1) & 1] = c[1].query(p[i]) + val[i];
		c[0].modify(p[i], f[i][0], i);
		c[1].modify(p[i], f[i][1], i);
	}
	for (int i = n; i >= 1; --i) suf[i] = suf[i + 1] + val[i] - 1;
	c[0].sss(); c[1].sss();
	ans = min(solve1(), solve2());
	if (ans[0] == inf) {
		printf("-1"); return 0;
	}
	for (auto i: ans) printf("%d", i);
}