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;
const int inf = 0x3f3f3f3f;
int main()
{
#ifdef wxh010910
	freopen("input.txt", "r", stdin);
#endif
	int n;
	cin >> n;
	vector<int> a(n);
	vector<bool> b(n);
	int prefix = -1, q = 0;
	for(int i = 0; i < n; ++i)
	{
		cin >> a[i];
		--a[i];
		if(a[i] > prefix)
		{
			prefix = a[i];
			b[i] = true;
			++q;
		}
	}
	vector<int> fenw_even(n, 0), fenw_odd(n, -inf);
	stack< pair<int *, int> > memory;
	auto modify = [&](vector<int> & fenw, int x, int value)
	{
		while(x < n)
		{
			if(fenw[x] < value)
			{
				memory.emplace(& fenw[x], fenw[x]);
				fenw[x] = value;
			}
			x |= x + 1;
		}
	};
	auto query = [&](vector<int> & fenw, int x)
	{
		int result = - inf;
		while(x >= 0)
		{
			result = max(result, fenw[x]);
			x = (x & (x + 1)) - 1;
		}
		return result;
	};
	vector<int> size(n);
	for(int i = n - 1; ~ i; --i)
	{
		int even = -inf, odd = -inf;
		size[i] = memory.size();
		if(b[i])
		{
			even = query(fenw_even, n - a[i] - 1) + 2;
			odd = query(fenw_odd, n - a[i] - 1) + 2;
		}
		else
		{
			even = query(fenw_odd, n - a[i] - 1) + 1;
			odd = query(fenw_even, n - a[i] - 1) + 1;
		}
		if(even >= 0)
		{
			modify(fenw_even, n - a[i] - 1, even);
		}
		if(odd >= 0)
		{
			modify(fenw_odd, n - a[i] - 1, odd);
		}
	}
	auto check = [&](int x, int need)
	{
		if(need < 0) return false;
		if(need & 1)
		{
			return query(fenw_odd, n - x - 1) >= need;
		}
		else
		{
			return query(fenw_even, n - x - 1) >= need;
		}
	};
	auto valid = [&](int max0, int max1, int diff, int q)
	{
		return check(max0, q - diff) || check(max1, q + diff);
	};
	int max0 = 0, max1 = 0;
	if(!check(0, q))
	{
		puts("-1");
		return 0;
	}
	int diff = 0;
	for(int i = 0; i < n; ++i)
	{
		if(b[i]) --q;
		while(memory.size() > size[i])
		{
			* memory.top().first = memory.top().second;
			memory.pop();
		}
		if(max0 <= a[i])
		{
			if(valid(a[i], max1, diff + 1, q))
			{
				cout << 0;
				max0 = a[i];
				++diff;
			}
			else
			{
				cout << 1;
				if(max1 <= a[i])
				{
					max1 = a[i];
					--diff;
				}
			}
		}
		else
		{
			if(valid(max0, max1, diff, q))
			{
				cout << 0;
			}
			else
			{
				cout << 1;
				if(max1 <= a[i])
				{
					max1 = a[i];
					--diff;
				}
			}
		}
	}
	cout << endl;
	return 0;
}