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 <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
using namespace std;
const int N = 200010;
int n, a[N], cntx, cnty, mxx, mxy, mx, cnt[N];
bool premx[N];
int ans[N];

struct SEG {
	int t[N * 4];
	void build(int u, int l, int r) {
		if(l >= r) { t[u] = -1e9; return ; }
		int mid = (l + r) >> 1;
		build(u * 2, l, mid), build(u * 2 + 1, mid + 1, r);
		t[u] = max(t[u * 2], t[u * 2 + 1]);
	}
	void mdy(int u, int l, int r, int x, int w) {
		if(l >= r) { t[u] = w; return ; }
		int mid = (l + r) >> 1;
		x <= mid ? mdy(u * 2, l, mid, x, w) : mdy(u * 2 + 1, mid + 1, r, x, w);
		t[u] = max(t[u * 2], t[u * 2 + 1]);
	}
	int qry(int u, int l, int r, int L, int R) {
		if(R < l || L > r) return -1e9;
		if(L <= l && r <= R) return t[u];
		int mid = (l + r) >> 1;
		return max(qry(u * 2, l, mid, L, R), qry(u * 2 + 1, mid + 1, r, L, R));
	}
}; SEG t1, t2;

bool check(int x, int C) {
	if(C < 0) return 0;
	if(C & 1) return t1.qry(1, 1, n, x, n) >= C;
	return t2.qry(1, 1, n, x, n) >= C;
}
int main() {
	scanf("%d", &n);
	rep(i, 1, n) scanf("%d", &a[i]), premx[i] = (mx < a[i]), mx = max(mx, a[i]);
	t1.build(1, 1, n);
	per(i, n, 1) {
		int mx1 = t1.qry(1, 1, n, a[i], n);
		int mx2 = t2.qry(1, 1, n, a[i], n);
		if(premx[i]) t1.mdy(1, 1, n, a[i], mx1 + 2), t2.mdy(1, 1, n, a[i], mx2 + 2);
		else t1.mdy(1, 1, n, a[i], mx2 + 1), t2.mdy(1, 1, n, a[i], mx1 + 1);
	}
	per(i, n, 1) cnt[i] = cnt[i + 1] + premx[i];
	rep(i, 1, n) {
		t1.mdy(1, 1, n, a[i], -1e9), t2.mdy(1, 1, n, a[i], 0);
		if(check(mxy, cntx + cnt[i + 1] - cnty + (a[i] > mxx))) {
			ans[i] = 0;
			cntx += (a[i] > mxx), mxx = max(mxx, a[i]);
		}
		else if(check(max(mxx, a[i]), cnty + cnt[i + 1] - cntx - (a[i] > mxx))) {
			ans[i] = 0;
			cntx += (a[i] > mxx), mxx = max(mxx, a[i]);
		}
		else {
			ans[i] = 1;
			cnty += (a[i] > mxy), mxy = max(mxy, a[i]);
		}
	}
	if(cntx != cnty) puts("-1");
	else rep(i, 1, n) printf("%d", ans[i]);
	return 0;
}