WA on #11 #13

#include<cstdio>
#include<iostream>
#include<cstring>
#include<stack>
#define int long long
using namespace std;
const int N=1e3+10;
int n,a[N],suf[N],cnt=1;
struct Edge{
	int v,nxt;
}e[N*N];
int h[N],tot;
void add(int u,int v)
{
	e[++tot].v=v;
	e[tot].nxt=h[u];
	h[u]=tot;
}
int col[N];
stack<int>s1,s2;
int f=0;
void dfs(int u)
{
	for (int i=h[u];i;i=e[i].nxt)
	{
		int v=e[i].v;
		if (col[v]&&col[v]==col[u])
		{
			f=1;
			return;
		}
		if (!col[v])
		{
			col[v]=col[u]*-1;
			dfs(v);
		}
	}
}
signed main()
{
//	freopen("P1155_11.in","r",stdin);
	scanf("%lld",&n);
	for (int i=1;i<=n;i++) scanf("%lld",a+i);
	suf[n+1]=1145141919810;
	for (int i=n;i>=1;i--) suf[i]=min(a[i],suf[i+1]);
	for (int i=1;i<=n;i++)
	{
		for (int j=i+1;j<=n;j++)
		{
			if (a[i]<a[j]&&a[i]>suf[j+1]) add(i,j),add(j,i);
		}
	}
//	for (int i=1;i<=n;i++) printf("%lld ",suf[i]);
	for (int i=1;i<=n;i++)
	{
		if (!col[i])
		{
			col[i]=1;
			dfs(i);
		}
	}
	if (f)
	{
		printf("0\n");
		return 0;
	}
	for (int i=1;i<=n;++i)
	{
		if (col[i]==1)
		{
			s1.push(a[i]);
			printf("a ");
		}
		while (!s1.empty()&&s1.top()==cnt)
		{
			s1.pop();
			printf("b ");
			cnt++;
		}
		if (col[i]==-1)
		{
			s2.push(a[i]);
			printf("c ");
		}
		while (!s2.empty()&&s2.top()==cnt)
		{
			while (!s1.empty()&&s1.top()==cnt)
			{
				s1.pop();
				printf("b ");
				cnt++;
			}
			printf("d ");
			s2.pop();
			cnt++;
		}
	}
	while (!s1.empty()&&!s2.empty())
	{
		int d1=s1.top(),d2=s2.top();
		if (d1>d2)
		{
			printf("b ");
			s1.pop();
		}
		else
		{
			printf("d ");
			s2.pop();
		}
	}
	while (!s1.empty())
	{
		printf("b ");
		s1.pop();
	}
	while (!s2.empty())
	{
		printf("d ");
		s2.pop();
	}
}