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 meow(args...) fprintf(stderr, args)
typedef unsigned u32;
typedef long long s64;
typedef unsigned long long u64;
template<class T1, class T2> inline bool cmin(T1 &a, const T2 &b) {return b<a?(a=b, true):false;}
template<class T1, class T2> inline bool cmax(T1 &a, const T2 &b) {return a<b?(a=b, true):false;}
template<class Type> Type read() {
	Type a;
	bool b;
	unsigned char c;
	while(c=getchar()-48, (c>9)&(c!=253));
	for(a=(b=c==253)?0:c; (c=getchar()-48)<=9; a=a*10+c);
	return b?-a:a;
}
int (*rd)()=read<int>;

const int N=2e5+1;
int n, off, p[N], v[N], tr[2][1<<19];
char s[N];
int query(int *tr, int l) {
	int res=-1e9;
	for(l+=off; l; l/=2) if(~l&1) cmax(res, tr[l^1]);
	return res;
}
void modify(int *tr, int x, int v) {
	tr[x+=off]=v;
	while(x/=2) tr[x]=std::max(tr[2*x], tr[2*x+1]);
}
bool check(int x, int y) {
	return x>=0&&x<=query(tr[x&1], y);
}
int main() {
	int q=0, max[2]={}, cnt[2]={};
	n=rd();
	for(int i=1, max=0; i<=n; ++i) q+=v[i]=cmax(max, p[i]=rd());
	for(off=1; off<=n; off*=2);
	memset(tr[1], 192, 2*off*sizeof(int));
	for(int i=n; i>=1; --i) {
		int f[2];
		for(int j=0; j<2; ++j) f[j]=query(tr[j^v[i]^1], p[i])+v[i]+1;
		for(int j=0; j<2; ++j) modify(tr[j], p[i], f[j]);
	}
	if(!check(q, 0)) {
		puts("-1");
		return 0;
	}
	for(int i=1; i<=n; ++i) {
		int delta=cnt[1]-cnt[0]-(p[i]>max[0]);
		modify(tr[0], p[i], 0);
		modify(tr[1], p[i], -1e9);
		q-=v[i];
		int ans=!(check(q+delta, std::max(max[0], p[i]))||check(q-delta, max[1]));
		cnt[ans]+=cmax(max[ans], p[i]);
		s[i-1]=ans+'0';
	}
	puts(s);
	return 0;
}