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:
#ifndef BZ
#pragma GCC optimize "Ofast"
#endif
#include <bits/stdc++.h>
using namespace std;
using ull = uint64_t;
using ll = int64_t;
using ld = long double;

const int MAXN = 200228;
int a[MAXN];
bool must[MAXN];
int mustcnt[MAXN];

int bef[MAXN][2];


int n;
int fn;

struct Fen {

    Fen() {
        fill(begin(fen), end(fen), -MAXN);
    }

    int fen[MAXN];

    vector<pair<int, int>> changes;

    void upd(int x, int y) {
        for (int i = x; i <= fn + 1; i |= (i + 1)) {
            changes.emplace_back(i, fen[i]);
            fen[i] = max(fen[i], y);
        }
    }

    int gt(int x) {
        int ans = -MAXN;
        for (int i = x + 1; --i >= 0; i &= (i + 1)) {
            ans = max(ans, fen[i]);
        }

        return ans;
    }

    void pop(int sz) {
        while (changes.size() > sz) {
            fen[changes.back().first] = changes.back().second;
            changes.pop_back();
        }
    }
};

Fen fens[2];

bool good(int id, int x, int y, int d) {
    if (fens[0].gt(x) + d - mustcnt[id] < 0 || fens[0].gt(y) - d - mustcnt[id] < 0) {
        return false;
    }

    if (mustcnt[id] % 2 == d % 2) {
        return true;
    }

    return fens[1].gt(x) + d - mustcnt[id] >= 0 || fens[1].gt(y) - d - mustcnt[id] >= 0;
}

int main() {
#ifdef BZ
    freopen("input.txt", "r", stdin);
#endif
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cout.setf(ios::fixed); cout.precision(20);
    cin >> n;
    fn = n + 2;
    int cm = n + 2;
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
        a[i] = n + 1 - a[i];
        must[i] = a[i] < cm;
        cm = min(cm, a[i]);
    }

    fens[0].upd(0, 0);

    for (int i = n - 1; i >= 0; --i) {
        mustcnt[i] = mustcnt[i + 1] + must[i];
        for (int j = 0; j < 2; ++j) {
            bef[i][j] = fens[j].changes.size();
        }

        for (int j = 0; j < 2; ++j) {   
            for (int k = j; k < 2; ++k) {
                int cur = fens[j].gt(a[i] - 1);
                ++cur;
                cur += must[i];
                if (must[i] && k > j) {
                    continue;
                }

                fens[k].upd(a[i], cur);
            }
        }
    }

    if (!good(0, n, n, 0)) {
        cout << "-1\n";
        return 0;
    }

    int x = fn + 2, y = fn + 2, d = 0;

    for (int i = 0; i < n; ++i) {
        int id = i + 1;

        for (int j = 0; j < 2; ++j) {
            fens[j].pop(bef[i][j]); 
        }
 
        {
            int nx = x, ny = y, nd = d;
            if (a[i] < nx) {
                nx = a[i];
                ++nd;
            }

            if (good(id, nx, ny, nd)) {
                cout << 0;
                x = nx;
                y = ny;
                d = nd;
                continue;
            }
        }

        {
            int nx = x, ny = y, nd = d;
            if (a[i] < ny) {
                ny = a[i];
                --nd;
            }

            if (good(id, nx, ny, nd)) {
                cout << 1;
                x = nx;
                y = ny;
                d = nd;
                continue;
            }
        }

        assert(false);
    }


    assert(d == 0);

    cout << "\n";
}