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 <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int Maxn = 200010;
const int inf = 1<<23;
int a[Maxn], n, b[Maxn];
int seg[2][Maxn<<2];
int ans[Maxn];
void build_tree(int now, int L, int R) {
	seg[0][now] = seg[1][now] = -inf;
	if(L < R){
		int mid = L+R>>1, lc = now<<1, rc = now<<1|1;
		build_tree(lc, L, mid);
		build_tree(rc, mid+1, R);
	}
}
int _max(int x, int y) { return x > y ? x : y; }
int _min(int x, int y) { return x < y ? x : y; }
void chg(int op, int now, int L, int R, int x, int k) {
	if(L == R){ seg[op][now] = k; return; }
	int mid = L+R>>1, lc = now<<1, rc = now<<1|1;
	if(x <= mid) chg(op, lc, L, mid, x, k);
	else chg(op, rc, mid+1, R, x, k);
	seg[op][now] = _max(seg[op][lc], seg[op][rc]);
}
int qry(int op, int now, int L, int R, int l, int r) {
	if(L == l && R == r) return seg[op][now];
	int mid = L+R>>1, lc = now<<1, rc = now<<1|1;
	if(r <= mid) return qry(op, lc, L, mid, l, r);
	else if(l > mid) return qry(op, rc, mid+1, R, l, r);
	else return _max(qry(op, lc, L, mid, l, mid), qry(op, rc, mid+1, R, mid+1, r));
}
int main() {
	int i, j, k;
	scanf("%d", &n);
	for(i = 1; i <= n; i++) scanf("%d", &a[i]);
	int mx = 0, sum = 0;
	for(i = 1; i <= n; i++){
		b[i] = 1;
		if(a[i] > mx) b[i]++, mx = a[i], sum++;
	}
	a[n+1] = n+1;
	n++;
	build_tree(1, 1, n);
	chg(0, 1, 1, n, n, 0);
	for(i = n-1; i >= 1; i--){
		int o = b[i]&1;
		int p = qry(o, 1, 1, n, a[i]+1, n);
		if(p >= 0) chg(0, 1, 1, n, a[i], p+b[i]);
		p = qry(o^1, 1, 1, n, a[i]+1, n);
		if(p >= 0) chg(1, 1, 1, n, a[i], p+b[i]);
	}
	int c1 = 0, c2 = 0, h1 = 0, h2 = 0;
	sum--;
	chg(0, 1, 1, n, a[1], -inf); chg(1, 1, 1, n, a[1], -inf);
	if(qry((1+sum)&1, 1, 1, n, 1, n) >= 1+sum) c1++, h1 = a[1], ans[1] = 0;
	else if(qry((sum-1)&1, 1, 1, n, a[1]+1, n) >= sum-1) c2++, h2 = a[1], ans[1] = 1;
	else { printf("-1\n"); return 0; }
	for(i = 2; i <= n-1; i++){
		if(b[i] == 2) sum--;
		chg(0, 1, 1, n, a[i], -inf); chg(1, 1, 1, n, a[i], -inf);
		int nc, nh;
		if(a[i] > h1) nc = c1+1, nh = a[i];
		else nc = c1, nh = h1;
		int p = inf;
		if(nc-c2+sum >= 0) p = _min(p, nc-c2+sum);
		if(c2-nc+sum >= 0) p = _min(p, c2-nc+sum);
		if(qry(p&1, 1, 1, n, h2+1, n) >= p){
			ans[i] = 0;
			c1 = nc; h1 = nh;
		} else {
			ans[i] = 1;
			if(a[i] > h2) c2++, h2 = a[i];
		}
	}
	for(i = 1; i <= n-1; i++) printf("%d", ans[i]);
	printf("\n");
	return 0;
}