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:
// orz yyb
#include <bits/stdc++.h>

using std::cerr;
using std::endl;

const int N = 2e5 + 233, INF = 1e9;

int n, A[N], B[N], pre, Q[N], cnt0, cnt1, max0, max1, ans[N];

struct SegTree {
  int max[N * 4];
  #define ls (p << 1)
  #define rs (ls | 1)
  #define mid ((L + R) >> 1)
  inline void init() {
    memset(max, 0xcf, sizeof(max));
  }
  void modify(int p, int x, int v, int L, int R) {
    if (L == R) return max[p] = v, void();
    if (x <= mid) modify(ls, x, v, L, mid);
    else modify(rs, x, v, mid + 1, R);
    max[p] = std::max(max[ls], max[rs]);
  }
  int query(int p, int l, int r, int L, int R) {
    if (l <= L && r >= R) return max[p];
    int ret = -INF;
    if (l <= mid) ret = std::max(ret, query(ls, l, r, L, mid));
    if (r > mid) ret = std::max(ret, query(rs, l, r, mid + 1, R));
    return ret;
  }
} seg[2];

inline int check(int x, int y) {
  if (y < 0) return 0;
  return seg[y & 1].query(1, x, n, 1, n) >= y;
}

int main() {
  // freopen("data", "r", stdin);
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", A + i);
    if (A[i] > pre) pre = A[i], B[i] = 2;
    else B[i] = 1;
  }
  seg[1].init();
  for (int i = n; i; --i) {
    int max0 = seg[0].query(1, A[i], n, 1, n), max1 = seg[1].query(1, A[i], n, 1, n);
    if (B[i] == 1) seg[0].modify(1, A[i], max1 + 1, 1, n), seg[1].modify(1, A[i], max0 + 1, 1, n);
    else seg[0].modify(1, A[i], max0 + 2, 1, n), seg[1].modify(1, A[i], max1 + 2, 1, n);
    Q[i] = Q[i + 1] + B[i] - 1;
  }
  for (int i = 1; i <= n; ++i) {
    seg[0].modify(1, A[i], 0, 1, n), seg[1].modify(1, A[i], -INF, 1, n);
    if (check(max1, cnt0 - cnt1 + Q[i + 1] + (A[i] > max0)) || check(std::max(max0, A[i]), cnt1 - cnt0 + Q[i + 1] - (A[i] > max0)))
      ans[i] = 0, cnt0 += A[i] > max0, max0 = std::max(max0, A[i]);
    else ans[i] = 1, cnt1 += A[i] > max1, max1 = std::max(max1, A[i]);
  }
  if (cnt0 != cnt1) printf("-1");
  else for (int i = 1; i <= n; ++i) printf("%d", ans[i]);
  putchar('\n');
  return 0;
}