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 EB emplace_back
#define B0 B[0]
#define B1 B[1]

const int N = 200054, INF = 0x3f3f3f3f;

int n, Ac, Bc, Am = INT_MAX, Bm = INT_MAX;
int p[N];
bool prem[N];
char ans[N];

inline void up(int &x, const int y) {x < y ? x = y : 0;}
inline bool down(int &x, const int y) {return x > y ? x = y, 1 : 0;}
inline int min(const int x, const int y) {return x < y ? x : y;}

class BIT {
	private:
		typedef std::pair <int *, int> ppi;
		int n, x[N];
		std::vector <ppi> history;
	public:
		typedef size_t stamp_t;
		BIT () : n(0) {}
		inline void init(int size, int val) {n = size, std::fill(x + 1, x + (n + 1), val), history.clear();}

		int max(int h) {int s = INT_MIN; for (; h > 0; h &= h - 1) up(s, x[h]); return s;}
		stamp_t upd(int h, int v) {for (; h <= n; h |= h - 1, ++h) if (x[h] < v) history.EB(x + h, x[h]), x[h] = v; return history.size();}

		inline stamp_t stamp() {return history.size();}
		void undo(stamp_t t) {
			int *key, val;
			for (t = history.size() - t; t > 0; --t) std::tie(key, val) = history.back(), *key = val, history.pop_back();
		}
} B[2];

BIT::stamp_t rct0[N], rct1[N];

inline void push(int id, int bel) {ans[id] = bel | 48, bel ? Bc += down(Bm, p[id]) : Ac += down(Am, p[id]);}

int main() {
	int i, u, v, m = INT_MAX, all = 0; bool succ;
	scanf("%d", &n), B0.init(n, 0), B1.init(n, -INF);
	for (i = 0; i < n; ++i) scanf("%d", p + i), p[i] = n - p[i] + 1, all += prem[i] = down(m, p[i]);
	for (i = n - 1; i; --i) {
		u = B0.max(p[i]) + prem[i] + 1, v = B1.max(p[i]) + prem[i] + 1;
		if (u & 1) std::swap(u, v); assert(~u & v & 1);
		rct0[i] = B0.upd(p[i], u), rct1[i] = B1.upd(p[i], v);
	}
	for (i = 0; i < n; ++i) {
		all -= prem[i];
		B0.undo(rct0[i + 1]), B1.undo(rct1[i + 1]);
		m = Ac - Bc + (p[i] < Am) + all, succ  = m >= 0 && B[m & 1].max(min(Bm, n)) >= m;
		m = Bc - Ac - (p[i] < Am) + all, succ |= m >= 0 && B[m & 1].max(min(Am, n)) >= m;
		if (succ) push(i, 0);
		else {
			push(i, 1);
			m = Ac - Bc + all, succ  = m >= 0 && B[m & 1].max(min(Bm, n)) >= m;
			m = Bc - Ac + all, succ |= m >= 0 && B[m & 1].max(min(Am, n)) >= m;
			if (!succ) return puts("-1"), 0;
		}
	}
	assert(Ac == Bc);
	return puts(ans), 0;
}