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:
// I need some holiday
// But I don't wish that everyday is holiday
// Because I didn't bear the pain
// Because it wasn't a true freedom
//         ——『イヤホンと蝉時雨』·Orangestar

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef unsigned int UI;
typedef pair<int, int> pii;

#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#define MP make_pair
#define fst first
#define snd second
#define SZ(u) ((int) (u).size())
#define ALL(u) (u).begin(), (u).end()

inline void proc_status()
{
	ifstream t("/proc/self/status");
	cerr << string(istreambuf_iterator<char>(t), istreambuf_iterator<char>()) << endl;
}

template<typename T> inline int chkmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }
template<typename T> inline int chkmax(T &a, const T &b) { return b > a ? a = b, 1 : 0; }
template<typename T> inline T sqr(const T &val) { return val * val; }

namespace fastIO
{
	const int MAX_BUFFER_SIZE = 1 << 16;

	char buffer[MAX_BUFFER_SIZE], *cur = buffer, *ed = buffer;

	inline char getc() { return cur == ed && (ed = (cur = buffer) + fread(buffer, 1, MAX_BUFFER_SIZE, stdin), cur == ed) ? EOF : *cur++; }
}
using fastIO::getc;

template<typename T> inline T read()
{
	register T sum(0), fg(1);
	register char ch(getc());
	for(; !isdigit(ch); ch = getc()) if(ch == '-') fg = -1;
	for(;  isdigit(ch); ch = getc()) sum = sum * 10 - '0' + ch;
	return sum * fg;
}

inline char *read_str(char *s)
{
	register char ch(getc());
	while(!isgraph(ch)) ch = getc();
	for(; isgraph(ch); ch = getc()) *s++ = ch;
	*s = '\0';
	return s;
}

// END tpl.

const int INF = (int) 1e9;

const int MAXN = (int) 2e5;

int n;

int a[MAXN + 5];

inline void input()
{
	n = read<int>();
	for(int i = 1; i <= n; ++i) a[i] = read<int>();
}

struct SEGT
{
	static const int MAX_NODE = MAXN * 4;

	int mx[MAX_NODE + 5];

	inline void push_up(int u) { mx[u] = max(mx[u << 1], mx[u << 1 | 1]); }

	inline void build(int u, int l, int r, int val)
	{
		if(l == r)
		{
			mx[u] = val;
			return;
		}

		int mid = (l + r) / 2;
		build(u << 1, l, mid, val);
		build(u << 1 | 1, mid + 1, r, val);
		push_up(u);
	}

	inline void update(int u, int l, int r, int pos, int val)
	{
		if(l == r)
		{
			mx[u] = val;
			return;
		}

		int mid = (l + r) / 2;
		if(pos <= mid) update(u << 1, l, mid, pos, val);
		else update(u << 1 | 1, mid + 1, r, pos, val);
		push_up(u);
	}

	inline int query(int u, int l, int r, int ql, int qr)
	{
		if(ql <= l && r <= qr) return mx[u];

		int mid = (l + r) / 2;
		int res = -INF;
		if(ql <= mid) chkmax(res, query(u << 1, l, mid, ql, qr));
		if(mid < qr) chkmax(res, query(u << 1 | 1, mid + 1, r, ql, qr));
		return res;
	}
};

inline void solve()
{
	static int val[MAXN + 5], suf[MAXN + 5];;

	for(int res = 0, i = 1; i <= n; ++i) chkmax(res, a[i]), val[i] = a[i] == res ? 2 : 1;
	for(int i = n; i >= 1; --i) suf[i] = suf[i + 1] + (val[i] == 2);

	static SEGT T[2];

	for(int i = 0; i < 2; ++i) T[i].build(1, 1, n, i == 0 ? 0 : -INF);
	for(int i = n; i >= 1; --i)
	{
		int f[2];
		for(int j = 0; j < 2; ++j) f[(j + val[i]) % 2] = T[j].query(1, 1, n, a[i], n) + val[i];
		for(int j = 0; j < 2; ++j) T[j].update(1, 1, n, a[i], f[j]);
	}

	auto check = [] (int v, int lim) -> int
	{
		if(lim < 0) return 0;
		return T[lim & 1].query(1, 1, n, v, n) >= lim;
	};

	int mxX = 0, cntX = 0;
	int mxY = 0, cntY = 0;
	string ans = "";
	for(int i = 1; i <= n; ++i)
	{
		T[0].update(1, 1, n, a[i], 0);
		T[1].update(1, 1, n, a[i], -INF);
		if(check(mxY, suf[i + 1] + cntX + (a[i] > mxX) - cntY)) ans += '0', cntX += chkmax(mxX, a[i]);
		else if(check(max(mxX, a[i]), suf[i + 1] + cntY - (a[i] > mxX) - cntX)) ans += '0', cntX += chkmax(mxX, a[i]);
		else ans += '1', cntY += chkmax(mxY, a[i]);
	}
	if(cntX != cntY) puts("-1");
	else puts(ans.c_str());
}

int main()
{
#ifdef K_ON
	freopen("E.in", "r", stdin);
	freopen("E.out", "w", stdout);
#endif

	input();
	solve();

	return 0;
}