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;
using Int = long long;
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}


template <typename T,typename E>
struct SegmentTree{
  using F = function<T(T,T)>;
  using G = function<T(T,E)>;
  using H = function<E(E,E)>;
  Int n,height;
  F f;
  G g;
  H h;
  T ti;
  E ei;
  vector<T> dat;
  vector<E> laz;
  SegmentTree(F f,G g,H h,T ti,E ei):
    f(f),g(g),h(h),ti(ti),ei(ei){}
  
  void init(Int n_){
    n=1;height=0;
    while(n<n_) n<<=1,height++;
    dat.assign(2*n,ti);
    laz.assign(2*n,ei);
  }
  void build(const vector<T> &v){
    Int n_=v.size();
    init(n_);
    for(Int i=0;i<n_;i++) dat[n+i]=v[i];
    for(Int i=n-1;i;i--)
      dat[i]=f(dat[(i<<1)|0],dat[(i<<1)|1]);
  }
  inline T reflect(Int k){
    return laz[k]==ei?dat[k]:g(dat[k],laz[k]);
  }
  inline void eval(Int k){
    if(laz[k]==ei) return;
    laz[(k<<1)|0]=h(laz[(k<<1)|0],laz[k]);
    laz[(k<<1)|1]=h(laz[(k<<1)|1],laz[k]);
    dat[k]=reflect(k);
    laz[k]=ei;
  }
  inline void thrust(Int k){
    for(Int i=height;i;i--) eval(k>>i);
  }
  inline void recalc(Int k){    
    while(k>>=1)
      dat[k]=f(reflect((k<<1)|0),reflect((k<<1)|1));
  }
  void update(Int a,Int b,E x){
    thrust(a+=n);
    thrust(b+=n-1);
    for(Int l=a,r=b+1;l<r;l>>=1,r>>=1){
      if(l&1) laz[l]=h(laz[l],x),l++;
      if(r&1) --r,laz[r]=h(laz[r],x);
    }
    recalc(a);
    recalc(b);
  }
  void set_val(Int a,T x){
    thrust(a+=n);
    dat[a]=x;laz[a]=ei;
    recalc(a);
  }
  T query(Int a,Int b){
    thrust(a+=n);
    thrust(b+=n-1);
    T vl=ti,vr=ti;
    for(Int l=a,r=b+1;l<r;l>>=1,r>>=1) {
      if(l&1) vl=f(vl,reflect(l++));
      if(r&1) vr=f(reflect(--r),vr);
    }
    return f(vl,vr);
  }
};


struct FastIO{
  FastIO(){
    cin.tie(0);
    ios::sync_with_stdio(0);
  }
}fastio_beet;

//INSERT ABOVE HERE
signed main(){
  Int n;
  cin>>n;
  vector<Int> p(n);
  for(Int i=0;i<n;i++) cin>>p[i];

  vector<Int> latte(n);
  for(Int i=0,t=0;i<n;i++){
    latte[i]=(t<p[i]);
    chmax(t,p[i]);
  }

  Int k=0;
  for(Int i=0;i<n;i++) k+=latte[i];

  auto f=[](Int a,Int b){return max(a,b);};
  auto g=[](Int a,Int b){return a+b;};
  const Int INF = 1e9;
  SegmentTree<Int, Int> seg1(f,g,g,-INF,0);
  SegmentTree<Int, Int> seg2(f,g,g,-INF,0);

  vector<Int> vs(n+10,-INF);
  seg1.build(vs);
  seg2.build(vs);
 
  for(Int i=n-1;i>=0;i--){
    if(latte[i]){
      Int res1=seg1.query(p[i],n+10)+1;
      Int res2=seg2.query(p[i],n+10)+1;
      chmax(res1,1);
      
      seg1.update(0,n+10,-1);
      seg2.update(0,n+10,-1);
      
      seg1.set_val(p[i],res1);
      seg2.set_val(p[i],res2);
    }else{
      Int res1=seg1.query(p[i],n+10)+1;
      Int res2=seg2.query(p[i],n+10)+1;
      chmax(res1,1);
      
      seg2.set_val(p[i],max(res1,res2));
    }
  }
  
  Int a=0,b=0,c=0,d=0,e=0;
  
  auto check1=
    [&](){return min(a,b)+(k-c)>=max(a,b)&&(a+b+(k-c))%2==0;};
  auto check2=
    [&](Int d,Int e){
      
      if(a+seg2.query(d+1,n+10)>=b&&
         b+max(k-c,seg2.query(e+1,n+10))>=a) return true;
      
      if(b+seg2.query(e+1,n+10)>=a&&
         a+max(k-c,seg2.query(d+1,n+10))>=b) return true;
      
      return false;
    };
  
  if(!check1()&&!check2(d,e)){
    cout<<-1<<endl;
    return 0;
  }

  string s(n,'$');
  for(Int i=0;i<n;i++){        
    if(latte[i]){
      seg1.update(0,n+10,1);
      seg2.update(0,n+10,1);
      
      seg1.set_val(p[i],-INF);
      seg2.set_val(p[i],-INF);
    }else{
      seg2.set_val(p[i],-INF);
    }
    if(latte[i]) c++;
    Int pa=a,pb=b,pd=d,pe=e,flg=0;
    {
      a=pa;b=pb;d=pd;e=pe;
      s[i]='0';
      if(d<p[i]) a++;
      chmax(d,p[i]);
      flg|=(check1()||check2(d,e));
    }
    if(flg==0){
      a=pa;b=pb;d=pd;e=pe;
      s[i]='1';
      if(e<p[i]) b++;
      chmax(e,p[i]);
      flg|=(check1()||check2(d,e));
    }
    assert(flg);
  }
  
  cout<<s<<endl;
  return 0;
}