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<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<vector>
#include<map>
#include<set>
#include<string>
#include<queue>
#include<stack>
#include<complex>
#include<numeric>
using namespace std;
#define MOD 1000000007
#define MOD2 998244353
#define PRIM 3
#define INF (1<<29)
#define LINF (1LL<<60)
#define EPS (1e-10)
#define PI 3.1415926535897932384626433832795028
typedef long long Int;
typedef pair<Int, Int> P;
typedef long double Real;
typedef complex<Real> CP;

Int n;
Int p[220000];
bool high[220000];

Int odd[1 << 20];
Int even[1 << 20];

void set_val(Int *seg, Int pos, Int val){
    pos += 1 << 19;
    seg[pos] = val;
    while(pos >>= 1){
        seg[pos] = max(seg[pos * 2], seg[pos * 2 + 1]);
    }
}

Int max_val(Int *seg, Int l, Int r){
    Int ans = 0;
    l += 1 << 19;
    r += 1 << 19;
    while(l < r){
        if(l % 2 != 0){
            ans = max(ans, seg[l]);
            l++;
        }
        if(r % 2 != 0){
            r--;
            ans = max(ans, seg[r]);
        }
        l /= 2;
        r /= 2;
    }
    return ans;
}

int main(){
    cin >> n;
    int recent_max = -1;
    int high_cnt = 0;
    for(int i = 0;i < n;i++){
        cin >> p[i];
        if(p[i] > recent_max){            
            high_cnt++;
            recent_max = p[i];
            high[i] = true;
        }
    }


    for(int i = n-1;i >= 0;i--){
        int even_max = max_val(even, p[i] + 1, n + 2);
        int odd_max = max_val(odd, p[i] + 1, n + 2);
        if(high[i]){
            set_val(even, p[i], even_max + 2);
            if(odd_max != 0)
                set_val(odd, p[i],odd_max + 2);
        }
        else{
            set_val(odd, p[i], even_max + 1);
            if(odd_max != 0)
                set_val(even, p[i], odd_max + 1);
        }

    }
    
    int mx[2] = {-1, -1};
    int cnt[2] = {0, 0};
    string ans;
    for(int i = 0;i < n;i++){
        high_cnt -= high[i];
        set_val(even, p[i], 0);
        set_val(odd, p[i], 0);
        if(p[i] < mx[0] && p[i] < mx[1]){
            ans.push_back('0');
            continue;
        }

        {
            int tmp_cnt[2] = {cnt[0], cnt[1]};
            int tmp_max[2] = {mx[0], mx[1]};
            if(mx[0] < p[i]){
                tmp_cnt[0]++;
                tmp_max[0] = p[i];
            }
            bool ok = false;
            int diff0 = tmp_cnt[0] - tmp_cnt[1] + high_cnt;
            int diff1 = tmp_cnt[1] - tmp_cnt[0] + high_cnt;
            if(diff0 % 2 == 0 && 0 <= diff0 && diff0 <= max_val(even, tmp_max[1], n+2))ok = true;
            if(diff0 % 2 == 1 && 0 <= diff0 && diff0 <= max_val(odd, tmp_max[1], n+2))ok = true;
            if(diff1 % 2 == 0 && 1 <= diff1 && diff1 <= max_val(even, tmp_max[0], n+2))ok = true;
            if(diff1 % 2 == 1 && 1 <= diff1 && diff1 <= max_val(odd, tmp_max[0], n+2))ok = true;
            if(ok){
                cnt[0] = tmp_cnt[0];
                cnt[1] = tmp_cnt[1];
                mx[0] = tmp_max[0];
                mx[1] = tmp_max[1];
                ans.push_back('0');
                continue;
            }
        }
        
        {
            int tmp_cnt[2] = {cnt[0], cnt[1]};
            int tmp_max[2] = {mx[0], mx[1]};
            if(mx[1] < p[i]){
                tmp_cnt[1]++;
                tmp_max[1] = p[i];
            }
            bool ok = false;
            int diff0 = tmp_cnt[0] - tmp_cnt[1] + high_cnt;
            int diff1 = tmp_cnt[1] - tmp_cnt[0] + high_cnt;
            if(diff0 % 2 == 0 && 0 <= diff0 && diff0 <= max_val(even, tmp_max[1], n+2))ok = true;
            if(diff0 % 2 == 1 && 0 <= diff0 && diff0 <= max_val(odd, tmp_max[1], n+2))ok = true;
            if(diff1 % 2 == 0 && 1 <= diff1 && diff1 <= max_val(even, tmp_max[0], n+2))ok = true;
            if(diff1 % 2 == 1 && 1 <= diff1 && diff1 <= max_val(odd, tmp_max[0], n+2))ok = true;

            if(ok){
                cnt[0] = tmp_cnt[0];
                cnt[1] = tmp_cnt[1];
                mx[0] = tmp_max[0];
                mx[1] = tmp_max[1];
                ans.push_back('1');
                continue;
            }
        }
        cout << -1 << endl;
        return 0;
    }
    cout << ans << endl;
    return 0;
}