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 Rint register int
using namespace std;
const int N = 200003;
template<typename T>
inline void read(T &x){
	int ch = getchar(); x = 0;
	while(ch < '0' || ch > '9') ch = getchar();
	while(ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
}
template<typename T>
inline bool chkmax(T &a, const T &b){if(a < b) return a = b, 1; return 0;}
int n, a[N], mx, cnt[N];
bool val[N];
char s[N];
struct SegTree {
	int seg[N << 2];
	inline void build(int x, int L, int R){
		seg[x] = 1 - 1e9;
		if(L == R) return;
		int mid = L + R >> 1;
		build(x << 1, L, mid);
		build(x << 1 | 1, mid + 1, R);
	}
	inline void change(int x, int L, int R, int p, int v){
		if(L == R){seg[x] = v; return;}
		int mid = L + R >> 1;
		if(p <= mid) change(x << 1, L, mid, p, v);
		else change(x << 1 | 1, mid + 1, R, p, v);
		seg[x] = max(seg[x << 1], seg[x << 1 | 1]); 
	}
	inline int query(int x, int L, int R, int l, int r){
		if(l <= L && R <= r) return seg[x];
		int mid = L + R >> 1, ans = -1e9;
		if(l <= mid) ans = query(x << 1, L, mid, l, r);
		if(mid < r) chkmax(ans, query(x << 1 | 1, mid + 1, R, l, r));
		return ans;
	}
} Odd, Even;
inline bool check(int p, int v){
	if(v < 0) return false;
	if(v & 1) return Odd.query(1, 1, n, p, n) >= v;
	return Even.query(1, 1, n, p, n) >= v;
}
int main(){
	read(n);
	for(Rint i = 1;i <= n;++ i){
		read(a[i]); val[i] = chkmax(mx, a[i]);
	}
	Odd.build(1, 1, n);
	for(Rint i = n;i;-- i){
		int mx1 = Odd.query(1, 1, n, a[i], n), mx2 = Even.query(1, 1, n, a[i], n);
		if(val[i]) Odd.change(1, 1, n, a[i], mx1 + 2), Even.change(1, 1, n, a[i], mx2 + 2);
		else Odd.change(1, 1, n, a[i], mx2 + 1), Even.change(1, 1, n, a[i], mx1 + 1);
	}
	for(Rint i = n;i;-- i) cnt[i] = cnt[i + 1] + val[i];
	int cnt1 = 0, cnt2 = 0, mx1 = 0, mx2 = 0;
	for(Rint i = 1;i <= n;++ i){
		Odd.change(1, 1, n, a[i], 1 - 1e9); Even.change(1, 1, n, a[i], 0);
		if (check(mx2, cnt1 + cnt[i + 1] - cnt2 + (a[i] > mx1)) ||
			check(max(mx1, a[i]), cnt2 + cnt[i + 1] - cnt1 - (a[i] > mx1))){
			s[i] = '0'; cnt1 += chkmax(mx1, a[i]);
		} else {
			s[i] = '1'; cnt2 += chkmax(mx2, a[i]);
		}
	}
	if(cnt1 != cnt2) puts("-1");
	else puts(s + 1);
}