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 ll = long long;

template<typename A>
void out_(A a) {
	for(auto k : a) 
		std::cerr << k << ' ';
	std::cerr << '\n';
}

int const inf = 1e9;

void init(std::vector<int>& mx, int n, int val) {
	mx.resize(n * 2 + 5);
	for(int i = 0; i < n * 2 + 5; ++i)
		mx[i] = val;
}

void motifiy(std::vector<int>& mx, int k, int l, int r, int pos, int val) {
	if(l == r) {
		mx[k] = val;
		return ;
	}
	int mid = (l + r) >> 1;
	if(pos <= mid) 
		motifiy(mx, k << 1, l, mid, pos, val);
	else 
		motifiy(mx, k << 1 | 1, mid + 1, r, pos, val);
	mx[k] = std::max(mx[k << 1], mx[k << 1 | 1]);
}

int query(std::vector<int>& mx, int k, int l, int r, int _l, int _r) {
	if(l == _l && r == _r)
		return mx[k];
	int mid = (l + r) >> 1;
	if(_r <= mid)
		return query(mx, k << 1, l, mid, _l, _r);
	if(_l > mid)
		return query(mx, k << 1 | 1, mid + 1, r, _l, _r);
	return std::max(query(mx, k << 1, l, mid, _l, mid), query(mx, k << 1 | 1, mid + 1, r, mid + 1, _r));
}

int main() {
	std::ios::sync_with_stdio(0);
	int n;
	std::cin >> n;
	std::vector<int> a(n);
	for(int i = 0; i < n; ++i)
		std::cin >> a[i];

	std::vector<int> b(n, 0);
	int mx = 0;
	for(int i = 0; i < n; ++i) {
		if(a[i] > mx) 
			b[i] = 2;
		else
			b[i] = 1;
		mx = std::max(mx, a[i]);
	}

	std::vector<int> fenw_odd, fenw_even;
	init(fenw_odd, (n + 1) * 2, -inf);
	init(fenw_even, (n + 1) * 2, 0);

	for(int i = n - 1; i >= 0; --i) {
		int odd = -inf, even = 0;
		if(b[i] == 1) {
			even = query(fenw_odd, 1, 1, n + 1, a[i] + 1, n + 1) + 1;
			odd = query(fenw_even, 1, 1, n + 1, a[i] + 1, n + 1) + 1;
		} else {
			even = query(fenw_even, 1, 1, n + 1, a[i] + 1, n + 1) + 2;
			odd = query(fenw_odd, 1, 1, n + 1, a[i] + 1, n + 1) + 2;
		}
		if(even > 0)
			motifiy(fenw_even, 1, 1, n + 1, a[i], even);
		if(odd > 0)
			motifiy(fenw_odd, 1, 1, n + 1, a[i], odd);
	}

	int sum = 0;
	for(int i = 0; i < n; ++i)
		sum += b[i] == 2;

	auto chk = [&] (int val, int need) -> bool {
		if(need < 0) 
			return 0;
		val = std::max(val, 1);
		if(need & 1) 
			return query(fenw_odd, 1, 1, n + 1, val, n + 1) >= need;
		else 
			return query(fenw_even, 1, 1, n + 1, val, n + 1) >= need;
	};

	if(chk(1, sum) == 0) {
		std::cout << -1 << '\n';
		return 0;
	}

	std::string ans;
	int diff = 0, mx0 = 0, mx1 = 0;
	for(int i = 0; i < n; ++i) {
		sum -= b[i] == 2;
		motifiy(fenw_odd, 1, 1, n + 1, a[i], -inf);
		motifiy(fenw_even, 1, 1, n + 1, a[i], 0);
		if(mx0 < a[i]) {
			if(chk(a[i], sum - (diff + 1)) || chk(mx1, sum + diff + 1)) {
				ans += '0';
				++diff;
				mx0 = a[i];
			} else {
				ans += '1';
				if(mx1 < a[i]) {
					--diff;
					mx1 = a[i];
				}
			}
		} else {
			if(chk(mx0, sum - diff) || chk(mx1, sum + diff)) 
				ans += '0';
			else {
				ans += '1';
				if(mx1 < a[i]) {
					--diff;
					mx1 = a[i];
				}
			}
		}
	}
	std::cout << ans << '\n';
	return 0;
}