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; 
int gi() { 
	int res = 0, w = 1; 
	char ch = getchar(); 
	while (ch != '-' && !isdigit(ch)) ch = getchar(); 
	if (ch == '-') w = -1, ch = getchar(); 
	while (isdigit(ch)) res = res * 10 + ch - '0', ch = getchar(); 
	return res * w; 
} 
const int INF = 1e9; 
const int MAX_N = 2e5 + 5;
int N, a[MAX_N], val[MAX_N]; 
#define lson (o << 1)
#define rson (o << 1 | 1)
struct SGT { 
	int mx[MAX_N << 2]; 
	void pushup(int o) { mx[o] = max(mx[lson], mx[rson]); } 
	void build(int o = 1, int l = 1, int r = N) { 
		if (l == r) return (void)(mx[o] = -INF);
		int mid = (l + r) >> 1; 
		build(lson, l, mid), build(rson, mid + 1, r); 
		pushup(o); 
	} 
	void mdf(int pos, int v, int o = 1, int l = 1, int r = N) { 
		if (l == r) return (void)(mx[o] = v); 
		int mid = (l + r) >> 1; 
		if (pos <= mid) mdf(pos, v, lson, l, mid); 
		else mdf(pos, v, rson, mid + 1, r); 
		pushup(o); 
	} 
	int qry(int ql, int qr, int o = 1, int l = 1, int r = N) { 
		if (ql <= l && r <= qr) return mx[o]; 
		int mid = (l + r) >> 1, res = -INF; 
		if (ql <= mid) res = max(res, qry(ql, qr, lson, l, mid)); 
		if (qr > mid) res = max(res, qry(ql, qr, rson, mid + 1, r)); 
		return res; 
	} 
} t[2]; 
int cnt[MAX_N]; 
bool check(int mx, int v) {
	if (v < 0) return 0; 
	int len = t[v & 1].qry(mx, N); 
	return len >= v; 
}

int main () { 
	N = gi(); 
	for (int i = 1, mx = 0; i <= N; i++) { 
		a[i] = gi(); 
		if (a[i] > mx) mx = a[i], val[i] = 2; 
		else val[i] = 1; 
	} 
	t[1].build(); 
	for (int i = N; i; i--) { 
		int mx0 = t[0].qry(a[i], N), mx1 = t[1].qry(a[i], N); 
		if (val[i] & 1) t[0].mdf(a[i], mx1 + 1), t[1].mdf(a[i], mx0 + 1); 
		else t[0].mdf(a[i], mx0 + 2), t[1].mdf(a[i], mx1 + 2); 
	} 
	for (int i = N; i; i--) cnt[i] = cnt[i + 1] + (val[i] == 2); 
	vector<int> ans; 
	int cntX = 0, cntY = 0, mxX = 0, mxY = 0; 
	for (int i = 1; i <= N; i++) { 
		t[1].mdf(a[i], -INF), t[0].mdf(a[i], 0); 
		int _1 = cntX, _2 = mxX; 
		if (a[i] > mxX) mxX = a[i], ++cntX; 
		if (check(mxY, cntX + cnt[i + 1] - cntY) || check(mxX, cntY + cnt[i + 1] - cntX)) ans.push_back(0); 
		else { 
			cntX = _1, mxX = _2; 
			if (a[i] > mxY) mxY = a[i], ++cntY; 
			ans.push_back(1); 
		} 
	}
	if (cntX != cntY) return puts("-1") & 0; 
	for (int i = 0; i < (int)ans.size(); i++) putchar(ans[i] + '0'); 
	putchar('\n'); 
    return 0; 
}