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;
struct BIT {
  vector<int> seg;
  vector<pair<int, int> > seq;
  BIT(int n) { seg.resize(n + 1); }
  void modify(int pos, int x)
  {
    for (; pos < seg.size(); pos += pos & -pos) {
      seq.emplace_back(pos, seg[pos]);
      seg[pos] = max(seg[pos], x);
    }
  }
  int query(int pos)
  {
    int res = INT_MIN;
    pos = min(pos, (int)seg.size() - 1);
    for (; pos; pos -= pos & -pos) {
      res = max(res, seg[pos]);
    }
    return res;
  }
  void pop(int x)
  {
    while (seq.size() > x) {
      seg[seq.back().first] = seq.back().second;
      seq.pop_back();
    }
  }
};
int main()
{
  do {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
  } while (false);
  int n, mn = INT_MAX;
  cin >> n;
  vector<int> arr(n), val(n);
  for (int i = 0; i < n; i++) {
    cin >> arr[i];
    arr[i] = n - arr[i] + 1;
    val[i] = arr[i] < mn;
    mn = min(mn, arr[i]);
  }
  vector<int> sum(n + 1);
  vector<array<int, 2> > en(n);
  vector<BIT> seg(2, BIT(n));
  for (int i = n - 1; i >= 0; i--) {
    sum[i] = sum[i + 1] + val[i];
    array<int, 2> tmp;
    for (int j = 0; j < 2; j++) {
      tmp[j] = max(0, seg[j].query(arr[i]));
      en[i][j] = seg[j].seq.size();
    }
    for (int j = 0; j < 2; j++) {
      int x = tmp[j] + val[i] + 1;
      seg[x & 1].modify(arr[i], x);
    }
  }
  array<int, 2> lis = {n + 1, n + 1}, len = {0, 0};
  string ans;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 2; j++) {
      seg[j].pop(en[i][j]);
    }
    for (int j = 0; j < 2; j++) {
      auto nxt_lis = lis, nxt_len = len;
      if (arr[i] < lis[j]) {
        nxt_lis[j] = arr[i];
        nxt_len[j]++;
      }
      bool ok = false;
      if (i == n - 1) {
        ok = nxt_len[0] == nxt_len[1];
      } else {
        for (int x = 0; x < 2; x++) {
          int goal = nxt_len[x] - nxt_len[x ^ 1] + sum[i + 1];
          if (goal >= 0 && seg[goal & 1].query(nxt_lis[x ^ 1]) >= goal) {
            ok = true;
          }
        }
      }
      if (ok) {
        ans += (char)(j + '0');
        lis = nxt_lis;
        len = nxt_len;
        break;
      }
    }
    if (ans.size() != i + 1) {
      cout << -1 << endl;
      return 0;
    }
  }
  cout << ans << endl;
  return 0;
}