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 LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template <class T>
istream& operator>>(istream& is, vector<T>& v) {
  for (T& x : v)
    is >> x;
  return is;
}

ostream& operator<<(ostream& os, const pair<char, int>& unit) {
  return os << unit.first << "^" << unit.second;
}

template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  if (!v.empty()) {
    os << v.front();
    for (int i = 1; i < v.size(); ++i)
      os << ' ' << v[i];
  }
  return os;
}

struct Node {
  int l, r, v;
  Node *ls, *rs;

  void ch(int k, int x) {
    if (l == r) {
      v = x;
      return;
    }
    (k <= ls->r ? ls : rs)->ch(k, x);
    v = max(ls->v, rs->v);
  }

  int qry(int l, int r) const {
    if (this->l == l && this->r == r)
      return v;
    if (r <= ls->r)
      return ls->qry(l, r);
    if (l >= rs->l)
      return rs->qry(l, r);
    return max(ls->qry(l, ls->r), rs->qry(rs->l, r));
  }
};

const int N = 200010;

int n;
int p[N];
int modify[N][2];
bool high[N];

Node* build(int l, int r, int val) {
  static Node pool[N * 4], *top = pool;
  Node* p = top++;
  p->l = l;
  p->r = r;
  p->v = val;
  if (l == r) return p;
  int mid = (l + r) >> 1;
  p->ls = build(l, mid, val);
  p->rs = build(mid + 1, r, val);
  return p;
}

int main() {
#ifdef LBT
  freopen("test.in", "r", stdin);
  int nol_cl = clock();
#endif
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  cin >> n;
  for (int i = 1; i <= n; ++i)
    cin >> p[i];
  int mx = 0;
  for (int i = 1; i <= n; ++i)
    if (mx < p[i]) {
      mx = p[i];
      high[i] = true;
    }
  static Node *segTree[2];
  segTree[0] = build(1, n + 1, 0);
  segTree[1] = build(1, n + 1, -n * 2 - 1);
  for (int i = n; i; --i) {
    for (int j = 0; j < 2; ++j)
      segTree[j]->ch(p[i], segTree[j ^ !high[i]]->qry(p[i] + 1, n + 1) + 1 + high[i]);
  }
  int cx = 0, cy = 0, hx = 0, hy = 0, q = count(high + 1, high + n + 1, true);
  if (segTree[q & 1]->qry(1, n + 1) >= q) {
    for (int i = 1; i <= n; ++i) {
      segTree[0]->ch(p[i], 0);
      segTree[1]->ch(p[i], -n * 2 - 1);
      int ncx = cx + (hx < p[i]);
      q -= high[i];
      if ((cy + q - ncx >= 0 && segTree[(cy + q - ncx) & 1]->qry(max(hx, p[i]) + 1, n + 1) >= cy + q - ncx) ||
          (ncx + q - cy >= 0 && segTree[(ncx + q - cy) & 1]->qry(hy + 1, n + 1) >= ncx + q - cy)) {
        cout << 0;
        if (hx < p[i]) {
          hx = p[i];
          ++cx;
        }
      } else {
        cout << 1;
        if (hy < p[i]) {
          hy = p[i];
          ++cy;
        }
      }
    }
  } else
    cout << -1;

#ifdef LBT
  LOG("Time: %dms\n", int ((clock()
      -nol_cl) / (double)CLOCKS_PER_SEC * 1000));
#endif
  return 0;
}