思路：
二分图染+模拟；
代码：
#include <bits/stdc++.h>
using namespace std;
#define maxn 1005
#define maxm 2000005
int n,head[maxn],E[maxm],V[maxm],cnt,col[maxn];
int minn[maxn],ai[maxn],sta1[maxn],sta2[maxn],top1,top2;
bool if_[maxn][maxn];
inline void in(int &now)
{
char Cget=getchar();now=;
while(Cget>''||Cget<'')Cget=getchar();
while(Cget>=''&&Cget<='')
{
now=now*+Cget-'';
Cget=getchar();
}
}
void edge_add(int u,int v)
{
E[++cnt]=head[u],V[cnt]=v,head[u]=cnt;
E[++cnt]=head[v],V[cnt]=u,head[v]=cnt;
}
bool dfs(int now,int dis,int fa)
{
if(col[now]) return true;
col[now]=dis+;
for(int i=head[now];i;i=E[i])
{
if(V[i]==fa) continue;
if(dfs(V[i],dis^,now)) return true;
}
return false;
}
int main()
{
in(n);
for(int i=;i<=n;i++) in(ai[i]);
minn[n]=ai[n];
for(int i=n-;i>=;i--) minn[i]=min(minn[i+],ai[i]);
for(int i=;i<n;i++)
{
for(int j=i+;j<n;j++)
{
if(minn[j+]<ai[i]&&ai[i]<ai[j])
{
if(!if_[i][j])
{
if_[i][j]=true;
if_[j][i]=true;
edge_add(i,j);
}
}
}
}
for(int i=;i<=n;i++)
{
if(!col[i])
{
if(dfs(i,,))
{
printf("");
return ;
}
}
}
int now=;
for(int i=;i<=n;i++)
{
if(ai[i]>now)
{
if(col[i]==) putchar('a'),sta1[++top1]=ai[i];
else putchar('c'),sta2[++top2]=ai[i];
}
else
{
now++;
if(col[i]==) printf("a b");
else printf("c d");
while()
{
if(sta1[top1]==now)
{
printf(" b"),top1--;
now++;continue;
}
if(sta2[top2]==now)
{
printf(" d"),top2--;
now++;continue;
}
break;
}
}
if(i!=n) putchar(' ');
}
while(top1--) printf(" b");
while(top2--) printf(" d");
return ;
}