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<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<ctime>
#include<map>
#include<bitset>
#include<set>
#define LL long long
#define mp(x,y) make_pair(x,y)
#define pll pair<long long,long long>
#define pii pair<int,int>
using namespace std;
inline int read()
{
	int f=1,x=0;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int stack[20];
inline void write(int x)
{
	if(x<0){putchar('-');x=-x;}
    if(!x){putchar('0');return;}
    int top=0;
    while(x)stack[++top]=x%10,x/=10;
    while(top)putchar(stack[top--]+'0');
}
inline void pr1(int x){write(x);putchar(' ');}
inline void pr2(int x){write(x);putchar('\n');}
const int MAXN=200005;
int n;
int lowbit(int x){return x&-x;}
struct bittree
{
	int s[MAXN];
	void modify(int x,int c){for(;x<=n;x+=lowbit(x))s[x]=max(s[x],c);}
	int qry(int x){int ret=0;for(;x>=1;x-=lowbit(x))ret=max(ret,s[x]);return ret;}
}bi[2];
int L[MAXN],R[MAXN],a[MAXN];
int is[MAXN],sum;
int re[2][MAXN][20];
void rebuild(int i)
{
	int u=n-a[i]+1;
	for(int x=u,cnt=1;x<=n;x+=lowbit(x),cnt++)bi[0].s[x]=re[0][i][cnt];
	for(int x=u,cnt=1;x<=n;x+=lowbit(x),cnt++)bi[1].s[x]=re[1][i][cnt];
}
void getit(int i)
{
	int u=n-a[i]+1;
	for(int x=u,cnt=1;x<=n;x+=lowbit(x),cnt++)re[0][i][cnt]=bi[0].s[x];
	for(int x=u,cnt=1;x<=n;x+=lowbit(x),cnt++)re[1][i][cnt]=bi[1].s[x];
}
void init()
{
	int mx=0;
	for(int i=1;i<=n;i++)if(a[i]>mx)is[i]=1,mx=a[i],sum++;
	for(int i=n;i>=1;i--)
	{
		int u=n-a[i]+1;
		int u1=bi[0].qry(u-1),u2=bi[1].qry(u-1);
		if(is[i])u1+=2,u2+=2;
		else u1+=1,u2+=1;
		getit(i);
		bi[u1&1].modify(u,u1);bi[u2&1].modify(u,u2);
	}
}
int ans[MAXN];
int mx[2],cnt[2];
bool ok(int i,int o)
{
	cnt[o]+=(a[i]>mx[o]);
	int u=n-mx[o^1]+1,c1=bi[0].qry(u-1),c2=bi[1].qry(u-1);
	int cal=cnt[o]-cnt[o^1]+sum;
	cnt[o]-=(a[i]>mx[o]);
	if(cal>=0)
	{
		if((cal&1)&&cal<=c2)return true;
		if((!(cal&1))&&cal<=c1)return true;
	}
	int ls=mx[o];
	cnt[o]+=(a[i]>mx[o]);mx[o]=max(mx[o],a[i]);
	u=n-mx[o]+1,c1=bi[0].qry(u-1),c2=bi[1].qry(u-1);
	cal=cnt[o^1]-cnt[o]+sum;
	mx[o]=ls;cnt[o]-=(a[i]>mx[o]);
	if(cal>=0)
	{
		if((cal&1)&&cal<=c2)return true;
		if((!(cal&1))&&cal<=c1)return true;
	}
	return false;
}
int main()
{
	n=read();
	for(int i=1;i<=n;i++)a[i]=read();
	init();
	for(int i=1;i<=n;i++)
	{
		rebuild(i);sum-=is[i];
		if(ok(i,0))ans[i]=0,cnt[0]+=(a[i]>mx[0]),mx[0]=max(mx[0],a[i]);
		else if(ok(i,1))ans[i]=1,cnt[1]+=(a[i]>mx[1]),mx[1]=max(mx[1],a[i]);
		else return puts("-1"),0;
	}
	for(int i=1;i<=n;i++)putchar(ans[i]+'0');
	puts("");
	return 0;
}