不能发现两个数$a_{j}, a_{k}\ \ (j < k)$不能放在同一个栈的充分必要条件时存在一个$i$使得$j < k < i$且$a_{i} < a_{j} < a_{k}$。
证明？写个dfs就证完了（就是考虑任意一个三元组）。
然后可建图，对于满足上面条件的$(j, k)$，$j$和$k$连一条无向边。
显然必要条件时图不存在奇环，即能够二分染色。
再证明一下这是必要条件。
我们先构造一个做法：硬点二分染色完白点扔第一个栈里，黑点扔第二个栈里，当当前需要输出的数能够输出的时候就输出，否则继续加数。
我们只需要证明每个数都能被正确的输出就行了。
显然第1个数一定能被正确地输出。
假设前$k - 1\ \ \ (k > 1)$个数已经被正确地输出了，考虑第$k$个数。
- 第$k$个数不在栈中，那么还剩在序列中，我们把之间的数加入栈中，再把它加入弹出，它就正确地输出了。
- 第$k$个数在栈中
- 某个栈的栈顶，直接弹出，正确地输出了。
- 否则它上面一定存在一个数$x > k$使得它无法弹出。
- 如果$1, 2, \dots, k - 1$中都在$k$之前，那么输出完前$k - 1$个数后，$k$入栈后就可以弹出并输出了，与做法矛盾。
- 否则存在一个$y < x$在$k$之后，由建图方法和染色可知$k, x$不能在同一个栈中，矛盾。
因此图能够二分染色是存在解的充分必要条件。
然后拿个栈直接贪心就好了。每次选择能够进行的字典序最小的操作。
Code
/**
* Vijos
* Problem#1605
* Accepted
* Time: 42ms
* Memory: 1.363m
*/
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;
typedef bool boolean; const int N = 1e3 + ; int n;
int ar[N];
int mns[N];
boolean g[N][N]; inline void init() {
scanf("%d", &n);
for (int i = ; i <= n; i++)
scanf("%d", ar + i);
} int col[N];
boolean color(int p, int col) {
if (::col[p] != -)
return ::col[p] == col;
::col[p] = col;
for (int i = ; i <= n; i++)
if (g[p][i] && !color(i, col ^ ))
return false;
return true;
} int s1[N], s2[N];
int tp1, tp2; inline void solve() {
mns[n] = ar[n];
for (int i = n - ; i; i--)
mns[i] = min(mns[i + ], ar[i]);
for (int i = ; i < n; i++)
for (int j = i + ; j < n; j++)
if (ar[i] < ar[j] && mns[j] < ar[i])
g[i][j] = g[j][i] = true;
memset(col, -, sizeof(col));
for (int i = ; i <= n; i++)
if (col[i] == - && !color(i, )) {
puts("");
return;
} int cur = , p = ;
while (cur <= n) {
if (p <= n && !col[p] && s1[tp1] != cur)
putchar('a'), s1[++tp1] = ar[p++];
else if (s1[tp1] == cur)
putchar('b'), tp1--, cur++;
else if (p <= n && col[p] && s2[tp2] != cur)
putchar('c'), s2[++tp2] = ar[p++];
else
putchar('d'), tp2--, cur++;
putchar(' ');
}
} int main() {
init();
solve();
return ;
}