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 inf = 0x3f3f3f3f;

int main() {
#ifdef wxh010910
  freopen("input.txt", "r", stdin);
#endif
  int n;
  cin >> n;
  vector<int> a(n);
  vector<bool> b(n);
  int prefix = -1, q = 0;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
    --a[i];
    if (a[i] > prefix) {
      prefix = a[i];
      b[i] = true;
      ++q;
    }
  }
  
  vector<int> fenw_even(n, 0), fenw_odd(n, -inf);
  stack<pair<int*, int>> memory;

  auto modify = [&](vector<int> &fenw, int x, int value) {
    while (x < n) {
      if (fenw[x] < value) {
        memory.emplace(&fenw[x], fenw[x]);
        fenw[x] = value;
      }
      x |= x + 1;
    }
  };

  auto query = [&](vector<int> &fenw, int x) {
    int result = -inf;
    while (x >= 0) {
      result = max(result, fenw[x]);
      x = (x & x + 1) - 1;
    }
    return result;
  };

  vector<int> size(n);
  for (int i = n - 1; ~i; --i) {
    int even = -inf, odd = -inf;
    size[i] = memory.size();
    if (b[i]) {
      even = query(fenw_even, n - a[i] - 1) + 2;
      odd = query(fenw_odd, n - a[i] - 1) + 2;
    } else {
      even = query(fenw_odd, n - a[i] - 1) + 1;
      odd = query(fenw_even, n - a[i] - 1) + 1;
    }
    if (even >= 0) {
      modify(fenw_even, n - a[i] - 1, even);
    }
    if (odd >= 0) {
      modify(fenw_odd, n - a[i] - 1, odd);
    }
  }

  auto check = [&](int x, int need) {
    if (need < 0) {
      return false;
    }
    if (need & 1) {
      return query(fenw_odd, n - x - 1) >= need;
    } else {
      return query(fenw_even, n - x - 1) >= need;
    }
  };

  auto valid = [&](int max0, int max1, int diff, int q) {
    return check(max0, q - diff) || check(max1, q + diff);
  };

  int max0 = 0, max1 = 0;
  if (!check(0, q)) {
    puts("-1");
    return 0;
  }
  int diff = 0;
  for (int i = 0; i < n; ++i) {
    if (b[i]) {
      --q;
    }
    while (memory.size() > size[i]) {
      *memory.top().first = memory.top().second;
      memory.pop();
    }
    if (max0 <= a[i]) {
      if (valid(a[i], max1, diff + 1, q)) {
        cout << 0;
        max0 = a[i];
        ++diff;
      } else {
        cout << 1;
        if (max1 <= a[i]) {
          max1 = a[i];
          --diff;
        }
      }
    } else {
      if (valid(max0, max1, diff, q)) {
        cout << 0;
      } else {
        cout << 1;
        if (max1 <= a[i]) {
          max1 = a[i];
          --diff;
        }
      }
    }
  }
  cout << endl;

  return 0;
}