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;

constexpr int INF = 1E9;
struct Maximum {
    int val[2];
    Maximum() : val {0, -INF} {}
    Maximum(int a, int b) : val {a, b} {}
};
Maximum operator+(const Maximum &a, const Maximum &b) {return Maximum(max(a.val[0], b.val[0]), max(a.val[1], b.val[1]));}

constexpr int M = 5E6;
struct Node {
    Node *c[2];
    Maximum val;
} nodes[M];

int cnt_nodes = 0;
Node *null = &nodes[0];
Node *newNode() {
    auto p = &nodes[++cnt_nodes];
    p->c[0] = p->c[1] = null;
    return p;
}
Node *insert(Node *p, int l, int r, int x, const Maximum &v) {
    auto q = newNode();
    q->val = p->val + v;
    if (r - l == 1)
        return q;
    int mid = (l + r) / 2;
    if (x < mid) {
        q->c[0] = insert(p->c[0], l, mid, x, v);
        q->c[1] = p->c[1];
    } else {
        q->c[0] = p->c[0];
        q->c[1] = insert(p->c[1], mid, r, x, v);
    }
    return q;
}
Maximum rangeMax(Node *p, int l, int r, int x, int y) {
    if (p == null || l >= y || r <= x)
        return Maximum();
    if (l >= x && r <= y)
        return p->val;
    int mid = (l + r) / 2;
    return rangeMax(p->c[0], l, mid, x, y) + rangeMax(p->c[1], mid, r, x, y);
}

int main() {
    null->c[0] = null->c[1] = null;
    
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n;
    cin >> n;
    vector<int> p(n);
    for (int i = 0; i < n; ++i) {
        cin >> p[i];
        --p[i];
    }
    
    vector<int> points(n);
    for (int i = 0, j = -1; i < n; ++i) {
        if (p[i] > j) {
            j = p[i];
            points[i] = 2;
        } else {
            points[i] = 1;
        }
    }
    
    vector<Node *> root(n + 1);
    root[n] = newNode();
    for (int i = n - 1; i >= 0; --i) {
        auto x = rangeMax(root[i + 1], 0, n, p[i] + 1, n);
        x.val[0] += points[i];
        x.val[1] += points[i];
        if (points[i] == 1)
            swap(x.val[0], x.val[1]);
        root[i] = insert(root[i + 1], 0, n, p[i], x);
    }
    vector<int> sum(n);
    for (int i = n - 1, j = 0; i >= 0; --i) {
        sum[i] = j;
        j += points[i] == 2;
    }
    
    vector<int> val[2], mx[2];
    mx[0] = mx[1] = {-1};
    int c[2] = {};
    string ans;
    for (int i = 0; i < n; ++i) {
        auto check = [&](int d) {
            int need = c[d] - c[d ^ 1] + sum[i];
            return need >= 0 && rangeMax(root[i + 1], 0, n, mx[d ^ 1].back() + 1, n).val[need % 2] >= need;
        };
        for (int d = 0; d <= 1; ++d) {
            val[d].push_back(p[i]);
            mx[d].push_back(max(mx[d].back(), p[i]));
            c[d] += mx[d].back() == p[i];
            if (check(0)) {
                ans += d + '0';
                break;
            }
            if (check(1)) {
                ans += d + '0';
                break;
            }
            c[d] -= mx[d].back() == p[i];
            val[d].pop_back();
            mx[d].pop_back();
        }
        if (ans.length() <= i) {
            cout << -1 << "\n";
            return 0;
        }
    }
    cout << ans << "\n";
    return 0;
}