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:

//#define USEPB_DS
#define USETR1
#define CPPELEVEN
#define GPP

/*
 * temp.cpp
 *
 *  Created on: 2012-7-18
 *      Author: BSBandme
 */
//#pragma comment(linker, "/STACK:1024000000,1024000000")

#include <bits/stdc++.h>

using namespace std;

#ifndef CPPELEVEN
#ifdef USETR1
#include <tr1/unordered_map>
#include <tr1/unordered_set>
using namespace tr1;
#endif
#else
#include <unordered_map>
#include <unordered_set>
#endif

#ifdef USEPB_DS
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
// binomial_heap_tag, rc_binomial_heap_tag, thin_heap_tag, binary_heap_tag
typedef __gnu_pbds::priority_queue<int, greater<int>, pairing_heap_tag> pq_type;
// splay_tree_tag, ov_tree_tag
typedef tree <int, null_type, less <int>, rb_tree_tag, tree_order_statistics_node_update> tree_type;
#endif

#define mpr make_pair
typedef unsigned int ui;
typedef unsigned long long ull;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <double, double> pdd;
typedef vector <int> vi;
typedef vector <ll> vll;
typedef vector <double> vd;
typedef vector <string> vs;
typedef map <string, int> mpsi;
typedef map <double, int> mpdi;
typedef map <int, int> mpii;

const double pi = acos(0.0) * 2.0;
const long double eps = 1e-10;
const int step[8][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}, {-1, 1}, {1, 1}, {1, -1}, {-1, -1}};

template <class T> inline T abs1(T a) {return a < 0 ? -a : a;}

#ifndef CPPELEVEN
template <class T> inline T max1(T a, T b) { return b < a ? a : b; }
template <class T> inline T max1(T a, T b, T c) { return max1(max1(a, b), c); }
template <class T> inline T max1(T a, T b, T c, T d) { return max1(max1(a, b, c), d); }
template <class T> inline T max1(T a, T b, T c, T d, T e) { return max1(max1(a, b, c, d), e); }
template <class T> inline T min1(T a, T b) { return a < b ? a : b; }
template <class T> inline T min1(T a, T b, T c) { return min1(min1(a, b), c); }
template <class T> inline T min1(T a, T b, T c, T d) { return min1(min1(a, b, c), d); }
template <class T> inline T min1(T a, T b, T c, T d, T e) { return min1(min1(a, b, c, d), e); }
#else
template <typename t, typename t1>
t min1(t a, t1 b) { return a < b ? a : b; }
template <typename t, typename... arg>
t min1(t a, arg... arr) { return min1(a, min1(arr...)); }
template <typename t, typename t1>
t max1(t a, t1 b) { return a > b ? a : b; }
template <typename t, typename... arg>
t max1(t a, arg... arr) { return max1(a, max1(arr...)); }
#endif

inline int jud(double a, double b){
  if(abs(a) < eps && abs(b) < eps) return 0;
  else if(abs1(a - b) / max(abs1(a), abs1(b)) < eps) return 0;
  if(a < b) return -1;
  return 1;
}
template <typename t> inline int jud(t a, t b){
  if(a < b) return -1;
  if(a == b) return 0;
  return 1;
}

// f_lb == 1代表返回相同的一串的左边界，f_small == 1代表返回如果没有寻找的值返回小的数
template <typename it, typename t1>
inline int find(t1 val, it a, int na, bool f_small = 1, bool f_lb = 1){
  if(na == 0) return 0;
  int be = 0, en = na - 1;
  if(*a <= *(a + na - 1)){
    if(f_lb == 0) while(be < en){
      int mid = (be + en + 1) / 2;
      if(jud(*(a + mid), val) != 1) be = mid;
      else en = mid - 1;
    }else while(be < en){
      int mid = (be + en) / 2;
      if(jud(*(a + mid), val) != -1) en = mid;
      else be = mid + 1;
    }
    if(f_small && jud(*(a + be), val) == 1) be--;
    if(!f_small && jud(*(a + be), val) == -1) be++;
  } else {
    if(f_lb) while(be < en){
      int mid = (be + en + 1) / 2;
      if(jud(*(a + mid), val) != -1) be = mid;
      else en = mid - 1;
    }else while(be < en){
      int mid = (be + en) / 2;
      if(jud(*(a + mid), val) != 1) en = mid;
      else be = mid + 1;
    }
    if(!f_small && jud(*(a + be), val) == -1) be--;
    if(f_small && jud(*(a + be), val) == 1) be++;
  }
  return be;
}

template <class T> inline T lowb(T num) {return num & (-num); }
#ifdef GPP
inline int bitnum(ui nValue) { return __builtin_popcount(nValue); }
inline int bitnum(int nValue) { return __builtin_popcount(nValue); }
inline int bitnum(ull nValue) { return __builtin_popcount(nValue) + __builtin_popcount(nValue >> 32); }
inline int bitnum(ll nValue) { return __builtin_popcount(nValue) + __builtin_popcount(nValue >> 32); }
inline int bitmaxl(ui a) { if(a == 0) return 0; return 32 - __builtin_clz(a); }
inline int bitmaxl(int a) { if(a == 0) return 0; return 32 - __builtin_clz(a); }
inline int bitmaxl(ull a) { int temp = a >> 32; if(temp) return 32 - __builtin_clz(temp) + 32; return bitmaxl(int(a)); }
inline int bitmaxl(ll a) { int temp = a >> 32; if(temp) return 32 - __builtin_clz(temp) + 32; return bitmaxl(int(a)); }
#else
#endif

long long pow(long long n, long long m, long long mod = 0){
  if(m < 0) return 0;
  long long ans = 1;
  long long k = n;
  while(m){
    if(m & 1) {
      ans *= k;
      if(mod) ans %= mod;
    }
    k *= k;
    if(mod) k %= mod;
    m >>= 1;
  }
  return ans;
}

#define  MOD 1000000007
template <class t1, class t2>
inline void add(t1 &a, t2 b, int mod = -1) {
  if(mod == -1) mod = MOD;
  a += b;
  while(a >= mod) a -= mod;
  while(a < 0) a += mod;
}
template <class t>
void output1(t arr) {
  for(int i = 0; i < (int)arr.size(); i++)
    cerr << arr[i] << ' ';
  cerr << endl;
}
template <class t>
void output2(t arr) {
  for(int i = 0; i < (int)arr.size(); i++)
    output1(arr[i]);
}

//....................密..........封..........线..........下..........禁..........止..........hack...............................................

const int maxn = 200100;
int n, orig[maxn];
int is_st[maxn];

#ifndef N
#define N maxn
#endif
#define SEG_TYPE ll

struct segment_node{
  int be, en;
  SEG_TYPE maxv;
};

struct segment_tree{
  int l;
  segment_node tree[N * 4];

  inline int gleft(int no) {return no << 1;}
  inline int gright(int no) {return (no << 1) + 1;}
  inline int gfa(int no) {return no >> 1;}
  inline segment_tree(){ l = 0; }

  void Build(int no, int l, int r, SEG_TYPE orig = 0, SEG_TYPE *a = NULL){
    if(l > r) r = l;
    if(l == r){
      tree[no].be = tree[no].en = l;
      if(a == NULL) tree[no].maxv = orig;
      else tree[no].maxv = a[l];
      return;
    }
    tree[no].be = l; tree[no].en = r;
    int mid = (l + r) / 2;
    Build(gleft(no), l, mid, orig, a);
    Build(gright(no), mid + 1, r, orig, a);
    tree[no].maxv = max1(tree[gleft(no)].maxv, tree[gright(no)].maxv);
  }

  inline void PushUp(int no) {
    tree[no].maxv = max1(tree[gleft(no)].maxv, tree[gright(no)].maxv);
  }

  void Upd(int l, int no, SEG_TYPE ranv){
    if(l <= tree[no].be && l >= tree[no].en){
      tree[no].maxv = ranv;
      return;
    }
    int mid = (tree[no].be + tree[no].en) >> 1;
    if(l <= mid) Upd(l, gleft(no), ranv);
    else Upd(l, gright(no), ranv);
    PushUp(no);
  }

  SEG_TYPE GetMaxv(int l, int r, int no){
    if(l > r) return 0;
    if(l <= tree[no].be && r >= tree[no].en)
      return tree[no].maxv;
    SEG_TYPE ans = 0;
    int mid = (tree[no].be + tree[no].en) >> 1;
    if(r >= tree[no].be && l <= mid)
      ans = max(ans, GetMaxv(l, r, gleft(no)));
    if(r >= mid + 1 && l <= tree[no].en)
      ans = max(ans, GetMaxv(l, r, gright(no)));
    return ans;
  }
} sgt[2];



int main() {


//............................不要再忘了检查maxn大小了！！！！BSBandme你个SB！！！！...................................................

  ios_base::sync_with_stdio(0);
  #ifdef DEBUG //......................................................................................................
  freopen("input.txt", "r", stdin);
  #endif //...........................................................................................................

  scanf("%d", &n);
  for (int i = 0; i < n; i++) scanf("%d", orig + i);

  sgt[0].Build(1, 1, n);
  sgt[1].Build(1, 1, n);

  is_st[0] = 1;
  int all = 1;
  for (int i = 1, last = 0; i < n; i++) {
    if (orig[i] > orig[last]) {
      last = i;
      all++;
      is_st[i] = 1;
    }
  }

  for (int i = n - 1; i >= 0; i--) {
    int v[2];
    v[!is_st[i]] = sgt[0].GetMaxv(orig[i] + 1, n, 1) + 1 + is_st[i];
    v[is_st[i]] = sgt[1].GetMaxv(orig[i] + 1, n, 1);
    if (v[is_st[i]]) v[is_st[i]] += 1 + is_st[i];
    sgt[0].Upd(orig[i], 1, v[0]);
    sgt[1].Upd(orig[i], 1, v[1]);
  }

  string ans(n, '0');
  int maxv[2] = {0, 0}, cnt[2] = {0, 0}, left = all;
  for (int j = 0; j < n; j++) {
    sgt[0].Upd(orig[j], 1, 0);
    sgt[1].Upd(orig[j], 1, 0);
    int rmaxv0 = maxv[0];
    cnt[0] += orig[j] > maxv[0];
    maxv[0] = max(maxv[0], orig[j]);
    left -= is_st[j];
    auto check = [&](int cnt[2], int maxv[2]) {
      int cate = abs((cnt[0] - cnt[1] + left) % 2);
      return (cnt[0] + left - cnt[1] >= 0 && cnt[0] - cnt[1] + left <=
          sgt[cate].GetMaxv(maxv[1] + 1, n, 1)) ||
          // Check here is for the case that sgt[0].GetMaxv are all high
          // elements and sgt[0].GetMaxv - sgt[1].GetMaxv > 1. e.g. the sample 3
          (cnt[1] + left - cnt[0] > 0 && cnt[1] + left - cnt[0] <=
              sgt[cate].GetMaxv(maxv[0] + 1, n, 1));
    };
    if (check(cnt, maxv)) {
      continue;
    }
    cnt[0] -= rmaxv0 < orig[j];
    maxv[0] = rmaxv0;
    cnt[1] += maxv[1] < orig[j];
    maxv[1] = max(maxv[1], orig[j]);
    if (check(cnt, maxv)) {
      ans[j] = '1';
    } else {
      cout << -1 << endl;
      return 0;
    }

  }
  cout << ans << endl;

  return 0;
}