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>
#define pa pair<int, int>
using namespace std;

int n, a[200010], f[200010][2], cnt = 0;
bool h[200010];
struct BIT
{
    vector<pa> s[200010];
    void insert(int x, int y, int pos)
    {
        for (int i = x; i <= n; i += i & -i)
        {
            if (s[i].empty() || s[i].back().second < y) s[i].emplace_back(pos, y);
        }
    }
    int get(int x, int pos)
    {
        int ans = 0xefefefef;
        for (int i = x; i > 0; i -= i & -i)
        {
            while (!s[i].empty() && s[i].back().first < pos) s[i].pop_back();
            if (!s[i].empty()) ans = max(ans, s[i].back().second);
        }
        return ans;
    }
} s[2];
char ans[200010];

bool chk(int x, int mx, int pos)
{
    if (x < 0) return false;
    if (x == 0) return true;
    if (mx == 0) mx = 1;
    int f[2] = {s[0].get(n - mx + 1, pos), s[1].get(n - mx + 1, pos)};/*
    printf("%d %d %d %d\n", pos, f[0], f[1], mx);
    for (int i = 1; i <= n; i++)
    {
        for (pa x : s[1].s[i])
            printf("(%d, %d)", x.first, x.second);
        puts("");
    }*/
    if (x & 1)
    {
        return f[1] >= x;
    }
    else
    {
        return f[1] >= x || f[0] >= x;
    }
}
int main()
{
    scanf("%d", &n);
    int mx = 0;
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
        if (a[i] > mx)
        {
            h[i] = true;
            mx = a[i];
            cnt++;
        }
    }
    for (int i = n; i > 0; i--)
    {
        if (h[i])
        {
            f[i][0] = max(2, s[0].get(n - a[i] + 1, i) + 2);
            f[i][1] = s[1].get(n - a[i] + 1, i) + 2;
            s[0].insert(n - a[i] + 1, f[i][0], i);
            s[1].insert(n - a[i] + 1, f[i][1], i);
        }
        else
        {
            f[i][1] = max(1, max(s[0].get(n - a[i] + 1, i), s[1].get(n - a[i] + 1, i)) + 1);
            s[1].insert(n - a[i] + 1, f[i][1], i);
        }
    }
    for (int i = n - 1; i > 0; i--)
    {
        f[i][0] = max(f[i][0], f[i + 1][0]);
        f[i][1] = max(f[i][1], f[i + 1][1]);
    }/*
    for (int i = 1; i <= n; i++)
    {
        printf("%d %d\n", f[i][0], f[i][1]);
    }
    puts("");*/
    if (!chk(cnt, 1, 1))
    {
        puts("-1");
        return 0;
    }
    int c = 0, mx1 = 0, mx2 = 0;
    for (int i = 1; i <= n; i++)
    {
        if (h[i]) cnt--;
        if (a[i] > mx1) c++;
        int hh1 = cnt + c, hh2 = cnt - c;
        // printf("%d %d %d %d %d %d %d\n", i, cnt, c, hh1, hh2, mx1, mx2);
        if (chk(hh1, mx2, i + 1) || chk(hh2, max(mx1, a[i]), i + 1))
        {
            mx1 = max(mx1, a[i]);
            ans[i] = '0';
        }
        else
        {
            if (a[i] > mx1) c--;
            if (a[i] > mx2) c--, mx2 = a[i];
            ans[i] = '1';
        }
    }
    puts(ans + 1);
}