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 <iostream>
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <time.h>
#include <stdlib.h>
#include <string>
#include <bitset>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <algorithm>
#include <sstream>
#include <stack>
#include <iomanip>
using namespace std;
#define pb push_back
#define mp make_pair
typedef pair<int,int> pii;
typedef long long ll;
typedef double ld;
typedef vector<int> vi;
#define fi first
#define se second
#define fe first
#define FO(x) {freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);}
#define Edg int M=0,fst[SZ],vb[SZ],nxt[SZ];void ad_de(int a,int b){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;}void adde(int a,int b){ad_de(a,b);ad_de(b,a);}
#define Edgc int M=0,fst[SZ],vb[SZ],nxt[SZ],vc[SZ];void ad_de(int a,int b,int c){++M;nxt[M]=fst[a];fst[a]=M;vb[M]=b;vc[M]=c;}void adde(int a,int b,int c){ad_de(a,b,c);ad_de(b,a,c);}
#define es(x,e) (int e=fst[x];e;e=nxt[e])
#define esb(x,e,b) (int e=fst[x],b=vb[e];e;e=nxt[e],b=vb[e])
#define SZ 666666
int n,p[SZ],g[SZ];
int mx[SZ][2],bb[2][SZ];
int qry(int*a,int t)
{
	int aa=-2.141e9;
	for(;t>=1;t-=t&-t)
		aa=max(aa,a[t]);
	return aa;
}
pair<int*,int> ed[5555555]; int en,dn[SZ];
void edt(int*a,int t,int u)
{
	for(;t<=n+1;t+=t&-t)
		if(a[t]<u) ed[++en]=mp(&a[t],a[t]),a[t]=u; 
}
bool chk(int t,int v)
{return t>=0&&qry(bb[t&1],v)>=t;}
int main()
{
	scanf("%d",&n);
	const int inf=int(2e9)+1;
	for(int i=1;i<=n+1;++i)
		bb[0][i]=0,bb[1][i]=-inf;
	mx[n+1][1]=-inf;
	for(int i=1;i<=n;++i)
		scanf("%d",p+i),
		p[i]=n+1-p[i];
	int mi=1e9;
	for(int i=1;i<=n;++i)
		mi=min(mi,p[i]),
		g[i]=1+(mi==p[i]);
	for(int i=n;i>=1;--i)
	{
		for(int j=0;j<2;++j)
			mx[i][j]=qry(bb[(j-g[i])&1],p[i])+g[i];
		for(int j=0;j<2;++j)
			edt(bb[j],p[i],mx[i][j]);
		dn[i]=en;
	}
	int cx=0,cy=0,Q=0;
	for(int i=1;i<=n;++i) Q+=(g[i]==2);
	if(!chk(Q,n+1))
	{
		puts("-1");
		return 0;
	}
	string s;
	int mx=n+1,my=n+1;
	for(int i=1;i<=n;++i)
	{
		Q-=(g[i]==2);
		int ox=p[i]<mx,oy=p[i]<my;
		while(en>dn[i+1])
			*ed[en].fi=ed[en].se,--en;
		if(chk((cx+ox-cy)+Q,my)
		||chk(-(cx+ox-cy)+Q,min(mx,p[i])))
			s.pb('0'),cx+=ox,mx=min(mx,p[i]);
		else if(chk((cy+oy-cx)+Q,mx)
		||chk(-(cy+oy-cx)+Q,min(my,p[i])))
			s.pb('1'),cy+=oy,my=min(my,p[i]);
		else throw "GG";
	}
	puts(s.c_str());
}