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 <algorithm>
    #include <iostream>
    #include <cstring>
    #include <cstdio>
    #include <set>
    const int N = 2e5 + 5; 
    const int INF = 1e9; 
    using namespace std;
     
    int n, m, p[N], val[N], cnt[N]; 
    char s[N]; 
     
    template < typename T >
    inline T read()
    {
    	T x = 0, w = 1; char c = getchar();
    	while(c < '0' || c > '9') { if(c == '-') w = -1; c = getchar(); }
    	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    	return x * w; 
    }
     
    struct SegTree
    {
    	struct Tree { int mx; } t[N << 2];
    	void build(int p, int l, int r)
    		{
    			if(l == r) { t[p].mx = 1 - INF; return; }
    			int mid = (l + r) >> 1; 
    			build(p << 1, l, mid), build(p << 1 | 1, mid + 1, r);
    			t[p].mx = max(t[p << 1].mx, t[p << 1 | 1].mx); 
    		}
    	int query(int p, int l, int r, int ql, int qr)
    		{
    			if(ql <= l && r <= qr) return t[p].mx; 
    			int mid = (l + r) >> 1; int ans = -INF; 
    			if(ql <= mid) ans = query(p << 1, l, mid, ql, qr); 
    			if(mid < qr) ans = max(ans, query(p << 1 | 1, mid + 1, r, ql, qr)); 
    			return ans; 
    		}
    	void modify(int p, int l, int r, int k, int x)
    		{
    			if(l == r) return (void) (t[p].mx = x); 
    			int mid = (l + r) >> 1; 
    			if(k <= mid) modify(p << 1, l, mid, k, x); 
    			else modify(p << 1 | 1, mid + 1, r, k, x); 
    			t[p].mx = max(t[p << 1].mx, t[p << 1 | 1].mx); 
    		}
    } Odd, Even; 
     
    bool check(int mx, int t)
    {
    	if(t < 0) return 0;
    	if(t & 1) return Odd.query(1, 1, n, mx, n) >= t;
    	else return Even.query(1, 1, n, mx, n) >= t; 
    }
     
    int main()
    {
    #ifndef ONLINE_JUDGE
    	freopen("cpp.in", "r", stdin); 
    #endif
    	n = read <int> ();
    	for(int mx = 0, i = 1; i <= n; i++)
    	{
    		p[i] = read <int> (); 
    		if(p[i] > mx) val[i] = 2, mx = p[i];
    		else val[i] = 1; 
    	}
    	Odd.build(1, 1, n); 
    	for(int mx1, mx2, i = n; i >= 1; i--)
    	{
    		mx1 = Odd.query(1, 1, n, p[i], n), mx2 = Even.query(1, 1, n, p[i], n); 
    		if(val[i] & 1) Odd.modify(1, 1, n, p[i], mx2 + val[i]), Even.modify(1, 1, n, p[i], mx1 + val[i]); 
    		else Odd.modify(1, 1, n, p[i], mx1 + val[i]), Even.modify(1, 1, n, p[i], mx2 + val[i]); 
    	}
    	for(int i = n; i >= 1; i--) cnt[i] = cnt[i + 1] + val[i] - 1; 
    	int cntx = 0, cnty = 0, mxx = 0, mxy = 0; 
    	for(int i = 1; i <= n; i++)
    	{
    		Odd.modify(1, 1, n, p[i], 1 - INF), Even.modify(1, 1, n, p[i], 0); 
    		if(check(mxy, cntx + cnt[i + 1] - cnty + (p[i] > mxx))) s[i] = '0', cntx += (p[i] > mxx), mxx = max(mxx, p[i]); 
    		else if(check(max(mxx, p[i]), cnty + cnt[i + 1] - cntx - (p[i] > mxx))) s[i] = '0', cntx += (p[i] > mxx), mxx = max(mxx, p[i]); 
    		else s[i] = '1', cnty += (p[i] > mxy), mxy = max(mxy, p[i]); 
    	}
    	if(cntx != cnty) puts("-1");
    	else printf("%s\n", s + 1); 
    	return 0;
    }