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;

const int N = 200000;
const int oo = 0x3f3f3f3f;

int n;
int a[N + 5], size[N + 5];
stack<pair<int*, int> > stk;

struct BIT {
#define lowbit(x) (x & -x)
    int c[N + 5]; 

    void clear() { memset(c, ~oo, sizeof c); }
    void modify(int x, int y) {
        while(x <= n) {
            if(c[x] < y) {
                stk.emplace(c + x, c[x]); 
            }
            c[x] = max(c[x], y);
            x += lowbit(x);
        }
    }

    int query(int x) {
        int res = c[N + 1];
        while(x > 0) {
            res = max(res, c[x]);
            x -= lowbit(x);
        }
        return res;
    }
};

BIT bit[2];
bool vis[N + 5];
vector<int> key;

bool chk(int A, int B, int x, int y, int c) {
    int t;
    t = B - A + c;
    if((t >= 0) && bit[t & 1].query(n - x) >= t) return true;
    t = A - B + c;
    if((t >= 0) && bit[t & 1].query(n - y) >= t) return true;
    return false;
}

int main() {

    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) {
        scanf("%d", a + i);

        if(key.empty() || a[i] > key.back()) {
            vis[i] = true;
            key.push_back(a[i]);
        }
    }

    bit[1].clear();
    for(int i = n; i >= 1; --i) {
        size[i] = stk.size();
        if(vis[i]) {
            bit[0].modify(n - a[i] + 1, bit[0].query(n - a[i]) + 2);
            bit[1].modify(n - a[i] + 1, bit[1].query(n - a[i]) + 2);
        } else {
            bit[0].modify(n - a[i] + 1, bit[1].query(n - a[i]) + 1);
            bit[1].modify(n - a[i] + 1, bit[0].query(n - a[i]) + 1);
        }
    }

    int c = key.size();
    if(bit[c & 1].query(n) < c) return puts("-1"), 0;

    int A = 0, B = 0, x = 0, y = 0;

    for(int i = 1; i <= n; ++i) {
        c -= vis[i];
        while((int) stk.size() > size[i]) {
            *stk.top().first = stk.top().second;
            stk.pop();
        }

        int nx = x, nA = A;
        if(a[i] > x) ++ A, x = a[i];
        
        if(chk(A, B, x, y, c)) {
            putchar('0');
            continue;
        }

        putchar('1');
        x = nx, A = nA;
        if(a[i] > y) ++ B, y = a[i];
    }

    return 0;
}