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 maxn 200005
using namespace std;
int f[maxn][2];
struct node{ int l, r, mx[2]; }tree[maxn * 4];
void build(int rt, int l, int r){
	tree[rt].l = l, tree[rt].r = r;
	if (l == r)
		return;
	build(rt << 1, l, l + r >> 1);
	build(rt << 1 | 1, (l + r >> 1) + 1, r);
}
void update(int rt, int x, int y){
	if (tree[rt].r < x || x < tree[rt].l)
		return;
	if (tree[rt].l == tree[rt].r){
		tree[rt].mx[0] = f[y][0], tree[rt].mx[1] = f[y][1];
		return;
	}
	update(rt << 1, x, y);
	update(rt << 1 | 1, x, y);
	tree[rt].mx[0] = max(tree[rt << 1].mx[0], tree[rt << 1 | 1].mx[0]);
	tree[rt].mx[1] = max(tree[rt << 1].mx[1], tree[rt << 1 | 1].mx[1]);
}
pair <int, int> query(int rt, int l, int r){
	if (tree[rt].r < l || r < tree[rt].l)
		return make_pair(0, 0);
	if (l <= tree[rt].l && tree[rt].r <= r)
		return make_pair(tree[rt].mx[0], tree[rt].mx[1]);
	pair <int, int> p1 = query(rt << 1, l, r), p2 = query(rt << 1 | 1, l, r);
	return make_pair(max(p1.first, p2.first), max(p1.second, p2.second));
}

int n, a[maxn], great[maxn], s[maxn];
bool check(int x, int to){
	if (to < 0)
		return false;
	pair <int, int> p = query(1, x + 1, n);
	if ((p.first - to & 1) == 0)
		return p.first >= to;
	else
		return p.second >= to;
}
int read(){
	int cnt = 0;
	char ch = getchar();
	while (ch < '0' || '9' < ch)
		ch = getchar();
	while ('0' <= ch && ch <= '9'){
		cnt = cnt * 10 + ch - '0';
		ch = getchar();
	}
	return cnt;
}
int main(){
	n = read();
	for (int i = 1; i <= n; ++ i)
		a[i] = read();
	for (int i = 1, mx = 0; i <= n; ++ i)
		if (a[i] > mx){
			mx = a[i];
			great[i] = true;
		}
	for (int i = n; i; -- i)
		s[i] = great[i] + s[i + 1];
	build(1, 1, n);
	for (int i = n; i; -- i){
		int t = 1 + great[i];
		pair <int, int> p = query(1, a[i] + 1, n);
		f[i][p.first + t & 1] = max(f[i][p.first + t & 1], p.first + t);
		f[i][p.second + t & 1] = max(f[i][p.second + t & 1], p.second + t);
		update(1, a[i], i);
	}
	if (! check(0, s[1])){
		cout << -1 << endl;
		return 0;
	}
	for (int i = 1, pos0 = 0, pos1 = 0, len0 = 0, len1 = 0; i <= n; ++ i){
		f[i][0] = f[i][1] = 0;
		update(1, a[i], i);
		int x = a[i] > a[pos0] ? i : pos0;
		int y = len0 + (x == i);
		if (check(a[x], len1 + s[i + 1] - y) || check(a[pos1], y + s[i + 1] - len1)){
			pos0 = x, len0 = y;
			printf("0");
		}
		else{
			pos1 = a[i] > a[pos1] ? i : pos1;
			len1 += pos1 == i;
			printf("1");
		}
	}
}