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 = 200233;
int n, p[N], sufMaxCnt[N], sufEvenScore[N], sufOddScore[N];
bool isPreMax[N];

vector<pair<int*, int>> undoStack;
int tOdd[N], tEven[N], undoSize[N];
void add(int *t, int x, int y) {
  for (x = n + 1 - x; x <= n; x += x & -x) {
    if (t[x] < y) {
      undoStack.emplace_back(&t[x], t[x]);
      t[x] = y;
    }
  }
}
int ask(int *t, int x) {
  int r = 0xc0c0c0c0;
  for (x = n + 1 - x; x; x -= x & -x) {
    r = max(r, t[x]);
  }
  return r;
}
bool check(int mx, int req) {
  if (req < 0) return false;
  return ask(req & 1 ? tOdd : tEven, mx) >= req;
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; i++) {
    scanf("%d", &p[i]);
  }
  int mx = 0;
  for (int i = 1; i <= n; i++) {
    mx = max(mx, p[i]);
    if (p[i] == mx) {
      isPreMax[i] = true;
    }
  }
  for (int i = n; i; i--) {
    sufMaxCnt[i] = sufMaxCnt[i + 1] + (int) isPreMax[i];
  }
  memset(tOdd, 0xc0, sizeof tOdd);
  for (int i = n; i; i--) {
    int sOdd = ask(tOdd, p[i]), sEven = ask(tEven, p[i]);
    undoSize[i] = (int) undoStack.size();
    if (isPreMax[i]) {
      sufEvenScore[i] = sEven + 2;
      sufOddScore[i] = sOdd < 0 ? 0xc0c0c0c0 : sOdd + 2;
    } else {
      sufEvenScore[i] = sOdd < 0 ? 0xc0c0c0c0 : sOdd + 1;
      sufOddScore[i] = sEven + 1;
    }
    if (sufOddScore[i] > 0) add(tOdd, p[i], sufOddScore[i]);
    add(tEven, p[i], sufEvenScore[i]);
  }
  if (!check(1, sufMaxCnt[1])) {
    puts("-1");
    return 0;
  }
  int max0 = 1, max1 = 1, diff = 0;
  for (int i = 1; i <= n; i++) {
    while ((int) undoStack.size() > undoSize[i]) {
      *undoStack.back().first = undoStack.back().second;
      undoStack.pop_back();
    }
    if (max0 <= p[i]) {
      if (check(max1, diff + 1 + sufMaxCnt[i + 1]) || check(p[i], sufMaxCnt[i + 1] - diff - 1)) {
        putchar('0');
        max0 = p[i];
        diff++;
      } else {
        putchar('1');
        if (max1 <= p[i]) {
          max1 = p[i];
          diff--;
        }
      }
    } else {
      if (check(max1, diff + sufMaxCnt[i + 1]) || check(max0, sufMaxCnt[i + 1] - diff)) {
        putchar('0');
      } else {
        putchar('1');
        if (max1 <= p[i]) {
          max1 = p[i];
          diff--;
        }
      }
    }
  }
}