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>
#define N 524288
int m,n;
inline int max(int x,int y){return x<y?y:x;}
inline void add(int*h,int u,int v){for(h[u|=m]=v;u>>=1;h[u]=max(h[u<<1],h[u<<1|1]));}
inline int sum(int*h,int u)
{
	int v=0x80000000;
	for(u|=m;u;u>>=1)if(~u&1)v=max(v,h[u^1]);
	return v;
}
int a[N],b[N],g[2][N],h[2][N],i,u,v,x,y;char e[N],f[N];
int main()
{
	scanf("%d",&n);
	for(m=1;m<n+2;m<<=1);
	for(i=1;i<m<<1;i++)h[1][i]=0x80000000;
	for(i=1;i<=n;i++)scanf("%d",a+i),b[i]=u<a[i]?u=a[i],1:0;
	for(i=n;i;i--) 
	if(b[i])add(h[0],a[i],sum(h[0],a[i])+2),add(h[1],a[i],sum(h[1],a[i])+2);
	else add(h[0],a[i],max(0,sum(h[1],a[i])+1)),add(h[1],a[i],sum(h[0],a[i])+1);
	for(i=n;i;i--)b[i]+=b[i+1];
	if(sum(h[b[1]&1],0)<b[1])return 0*puts("-1");
	for(i=1,u=0,memcpy(g,h,sizeof h);i<=n;i++)
	if(add(h[0],a[i],0x80000000),add(h[1],a[i],0x80000000),a[i]<u&&x<=b[i+1]+y&&b[i+1]+y-x<=sum(h[b[i+1]+y-x&1],u)||u<a[i]&&x+1<=b[i+1]+y&&b[i+1]+y-x-1<=sum(h[b[i+1]+y-x&1^1],a[i]))u=u<a[i]?x++,a[i]:u,e[i]=48;
	else v=v<a[i]?y++,a[i]:v,e[i]=49;
	for(i=1,u=v=x=y=0;i<=n;i++)
	if(add(g[0],a[i],0x80000000),add(g[1],a[i],0x80000000),a[i]<u&&y<=b[i+1]+x&&b[i+1]+x-y<=sum(g[b[i+1]+x-y&1],v)||u<a[i]&&y<=b[i+1]+x+1&&b[i+1]+x+1-y<=sum(g[b[i+1]+x-y&1^1],v))u=u<a[i]?x++,a[i]:u,f[i]=48;
	else v=v<a[i]?y++,a[i]:v,f[i]=49;
	return 0*printf("%s\n",strcmp(e+1,f+1)<0?e+1:f+1);
}