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;

namespace TYC
{
	typedef long long ll;
	const int N = 2e5 + 5;

	int n, flag, P[N], Mark[N], LIS[N][2];

	inline int read()
	{
		int x = 0;
		int f = 0, ch = getchar();
		while (!isdigit(ch))
			f |= (ch == '-'), ch = getchar();
		while (isdigit(ch))
			x = x * 10 + ch - '0', ch = getchar();
		return f ? -x : x;
	}

	struct tree
	{	
		int mxl, v[N << 3];
		void modify(const int p, const int w, const int t, const int o = 1, const int l = 1, const int r = n << 1);
		int query(const int w, const int o = 1, const int l = 1, const int r = n << 1);
		int getmax(const int p, const int w, const int o = 1, const int l = 1, const int r = n << 1);
	} T[2], V[2];

#define ls (o << 1)
#define rs (o << 1 | 1)

	void tree::modify(const int p, const int w, const int t, const int o, const int l, const int r)
	{
		if (l == r)
			return void(v[o] = t ? max(v[o], w) : w);
		int mid = (l + r) >> 1;
		p <= mid ? modify(p, w, t, ls, l, mid) : modify(p, w, t, rs, mid + 1, r);
		v[o] = max(v[ls], v[rs]);
	}

	int tree::query(const int w, const int o, const int l, const int r)
	{
		if (v[o] <= w)
			return 0;
		if (l == r)
			return l;
		int mid = (l + r) >> 1;
		return v[rs] > w ? query(w, rs, mid + 1, r) : query(w, ls, l, mid);
	}

	int tree::getmax(const int s, const int e, const int o, const int l, const int r)
	{
		if (s <= l && r <= e)
			return v[o];
		int mid = (l + r) >> 1, ans = 0;
		if (s <= mid)
			ans = max(ans, getmax(s, e, ls, l, mid));
		if (e > mid)
			ans = max(ans, getmax(s, e, rs, mid + 1, r));
		return ans;
	}

#undef ls
#undef rs

	void getlis()
	{
		for (int i = n; i; i--)
			if (Mark[i])
			{
				for (int k = 0; k < 2; k++)
				{
					int p = T[k].query(P[i]) + 2;
					if ((p & 1) == k)
					{
						T[k].mxl = max(T[k].mxl, p);
						T[k].modify(p, P[i], 1);
						LIS[i][k] = p;
					}
				}
			}
			else
			{
				for (int k = 0; k < 2; k++)
				{
					int p = T[k].query(P[i]) + 1;
					if ((p & 1) == (k ^ 1))
					{
						T[k ^ 1].mxl = max(T[k ^ 1].mxl, p);
						T[k ^ 1].modify(p, P[i], 1); 
						LIS[i][k ^ 1] = p;
					}
				}
			}
	}

	inline bool check(int cx, int hx, int cy, const int hy, int tot, const int i)
	{
		if (P[i] > hx)
			hx = P[i], cx++;
		int v = cy + tot - cx;
		if (v >= 0 && V[v & 1].getmax(hx, n) >= v)
			return true;
		v = cx + tot - cy;
		return v >= 0 && V[v & 1].getmax(hy, n) >= v;
	}

	void solve()
	{
		static char R[N];
		int cx = 0, cy = 0, hx = 0, hy = 0, tot = 0;
		for (int i = 1; i <= n; i++)
		{
			V[0].modify(P[i], LIS[i][0], 0);
			V[1].modify(P[i], LIS[i][1], 0);
			tot += Mark[i];
		}

		for (int i = 1; i <= n; i++)
		{
			V[0].modify(P[i], 0, 0);
			V[1].modify(P[i], 0, 0);
			tot -= Mark[i];
			if (check(cx, hx, cy, hy, tot, i))
			{
				R[i] = '0';
				if (P[i] > hx)
					hx = P[i], cx++;
			}
			else
			{
				R[i] = '1';
				if (P[i] > hy)
					hy = P[i], cy++;
			}
		}
		puts(cx != cy ? "-1" : R + 1);	
	}

	void work()
	{
		n = read();
		for (int i = 1; i <= n; i++)
			P[i] = read();
		for (int i = 1, mx = 0; i <= n; i++)
			if (P[i] > mx)
				mx = P[i], Mark[i] = 1;
		getlis();
		solve();
	}
}

int main()
{
	TYC::work();
	return 0;
}