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;

/// 17:19

const int Nmax = 2e5 + 5;

vector< vector< pair<int*, int> > > stk;
string ans;

bool high[Nmax];
int cost[Nmax], a[Nmax];
int n, i;

class AIB
{
    int a[Nmax];
    int ub(int x) { return (x&(-x)); }

public:
    int query(int x)
    {
        int ans = a[0];
        for(; x<=n; x+=ub(x)) ans = max(ans, a[x]);
        return ans;
    }

    void update(int p, int x)
    {
        for(; p; p-=ub(p))
            if(a[p] < x)
            {
                stk.back().push_back({a+p, a[p]});
                a[p] = x;
            }
    }

    void init(int val)
    {
        int i;
        for(i=0; i<=n; ++i) a[i] = val;
    }

} aib[2];

void build()
{
    int i, x, y;
    aib[0].init(0);
    aib[1].init(-1e9);

    for(i=n; i; --i)
    {
        stk.emplace_back();
        x = aib[0].query(a[i]);
        y = aib[1].query(a[i]);

        aib[cost[i]&1].update(a[i], x + cost[i]);
        aib[1^(cost[i]&1)].update(a[i], y + cost[i]);
    }
}

void refresh()
{
    for(auto it = stk.back().rbegin(); it != stk.back().rend(); ++it)
        *it->first = it->second;
    stk.pop_back();
}

bool check(int target, int last)
{
    if(target < 0) return 0;
    return aib[target&1].query(last+1) >= target;
}

int main()
{
   /// freopen("input", "r", stdin);
    cin.sync_with_stdio(false);

    cin >> n;
    for(i=1; i<=n; ++i) cin >> a[i];

    int Max = 0, cnt = 0;
    for(i=1; i<=n; ++i)
    {
        if(a[i] > Max) Max = a[i], high[i] = 1, ++cnt;
        cost[i] = high[i] + 1;
    }

    /*

    if((n&1) && cnt == n)
    {
        cout << "-1\n";
        return 0;
    }

    */

    build();

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

    int last1 = 0, last2 = 0, dif = 0, new_dif, new_last, new_cnt;

    for(i=1; i<=n; ++i)
    {
        refresh();

        new_last = last1, new_dif = dif, new_cnt = cnt;

        if(a[i] > new_last)
        {
            --new_dif;
            if(high[i]) --new_cnt;
            new_last = a[i];
        }

        if(check(new_cnt - new_dif, last2) || check(new_cnt + new_dif, new_last))
        {
            ans.push_back('0');
            last1 = new_last, dif = new_dif, cnt = new_cnt;
        }
        else
        {
            ans.push_back('1');
            if(a[i] > last2)
            {
                last2 = a[i];
                if(high[i]) --cnt;
                ++dif;
            }
        }
    }

    assert(!dif);
    cout << ans << '\n';
    return 0;
}