分析
因为要字典序最小，所以可以贪心，从前往后确定所有位，每位尽量填 $0$。
为了方便，我们把是 $p$ 中的前缀最大值的前缀最大值称作“旧的“，不是 $p$ 中前缀最大值的前缀最大值称作”新的“。
首先有一个结论：如果一个 $s$ 合法，那么 $x,y$ 两个序列中一定有一个序列的前缀最大值全都是旧的。
证明可以这样考虑：如果 $x,y$ 中都有一个新的前缀最大值，那么我们交换这两个数，这样子两个序列中就都少了一个新的。
那么我们不妨假设 $x$ 的前缀最大值全是旧的。
我们假设前 $i-1$ 位已经填完了，现在需要判定第 $i$ 位能否填 $0$。
设 $x$ 已经填的数中的前缀最大值有 $cx$ 个，$y$ 已经填的数中前缀最大值有 $cy$ 个，$p_{i..n}$ 中有 $c$ 个旧前缀最大值，$y$ 后面填的数中会有 $k$ 个旧前缀最大值、$m$ 个新前缀最大值，那么应该要有
$$
cx+c-k=cy+k+m
$$
即
$$
2k+m=cx+c-cy
$$
可以发现右边是常数，我们只要判断左边能否满足即可。
不难发现左边的意思其实是把旧前缀最大值看成 $2$、新前缀最大值看成 $1$，求能否在后面找到一个前缀最大值的和是右边的常数的一个子序列。可以发现，如果能找到一个前缀最大值的和是 $x$ 的子序列，那么一定能找到一个和是 $x-2$ 的，所以我们只要求出奇偶最大值即可。
考虑 DP。设 $dp_{i,0/1}$ 表示以 $i$ 开头、和是偶数/奇数的最大和，转移可以用线段树优化。
上面这个是 $x$ 不放的情况，$y$ 不放的情况类似，自己推一下式子即可。
代码
// ====================================
// author: M_sea
// website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;
int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=200000+10;
const int inf=0x3f3f3f40;
int n,a[N],w[N],cnt[N]; char s[N];
#define ls (o<<1)
#define rs (o<<1|1)
struct sgt {
int maxv[N<<2];
void pushup(int o) { maxv[o]=max(maxv[ls],maxv[rs]); }
void modify(int o,int l,int r,int p,int w) {
if (l==r) { maxv[o]=w; return; }
int mid=(l+r)>>1;
if (p<=mid) modify(ls,l,mid,p,w);
else modify(rs,mid+1,r,p,w);
pushup(o);
}
int query(int o,int l,int r,int ql,int qr) {
if (ql<=l&&r<=qr) return maxv[o];
int mid=(l+r)>>1,res=-inf;
if (ql<=mid) res=max(res,query(ls,l,mid,ql,qr));
if (qr>mid) res=max(res,query(rs,mid+1,r,ql,qr));
return res;
}
} odd,even;
#undef ls
#undef rs
bool check(int p,int w) {
if (w<0) return 0;
if (w&1) return odd.query(1,1,n,p,n)>=w;
else return even.query(1,1,n,p,n)>=w;
}
int main() {
n=read();
for (int i=1;i<=n;++i) a[i]=read();
for (int i=1,mx=0;i<=n;++i) {
if (a[i]>mx) w[i]=2,mx=a[i];
else w[i]=1;
}
memset(odd.maxv,0xc0,sizeof(odd.maxv));
for (int i=n;i;--i) {
int mxo=odd.query(1,1,n,a[i],n),mxe=even.query(1,1,n,a[i],n);
if (w[i]&1) odd.modify(1,1,n,a[i],mxe+w[i]),even.modify(1,1,n,a[i],mxo+w[i]);
else odd.modify(1,1,n,a[i],mxo+w[i]),even.modify(1,1,n,a[i],mxe+w[i]);
}
for (int i=n;i;--i) cnt[i]=cnt[i+1]+w[i]-1;
int cx=0,cy=0,mxx=0,mxy=0;
for (int i=1;i<=n;++i) {
odd.modify(1,1,n,a[i],-inf),even.modify(1,1,n,a[i],0);
if (check(mxy,cx+(a[i]>mxx)+cnt[i+1]-cy)
||check(max(mxx,a[i]),cy+cnt[i+1]-cx-(a[i]>mxx)))
s[i]='0',cx+=(a[i]>mxx),mxx=max(mxx,a[i]);
else s[i]='1',cy+=(a[i]>mxy),mxy=max(mxy,a[i]);
}
if (cx!=cy) puts("-1");
else for (int i=1;i<=n;++i) putchar(s[i]);
return 0;
}