Beyond the Void

/* 
 * Problem: NOIP2008 twostack
 * Author: Guo Jiabao
 * Time: 2008.12.9 21:22:52
 * State: Solved 
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
 
using namespace std;
 
const int MAXN=1002;
const int INF=0x7FFFFFFF;
 
class tStack
{
	private:
		int top;
		int S[MAXN];
	public:
		tStack() : top(0) {}
		void ins(int k)
		{
			S[++top]=k;
		}
		int tp()
		{
			return S[top];
		}
		void pop()
		{
			top--;
		}
};
 
int S[MAXN],F[MAXN],bel[MAXN];
bool adjm[MAXN][MAXN];
int N,top1,top2;
tStack T[3];
 
void init()
{
	int i;
	freopen("twostack.in","r",stdin);
	freopen("twostack.out","w",stdout);
	scanf("%d",&N);
	for (i=1;i<=N;i++)
	{
		scanf("%d",&S[i]);
	}
}
 
void noanswer()
{
	printf("0");
	exit(0);
}
 
void color(int i,int c)
{
	bel[i]=c;
	int j;
	for (j=1;j<=N;j++)
	{
		if (adjm[i][j])
		{
			if (bel[j]==c) //conflict : not a bipartite graph
			{
				noanswer();
			}
			if (!bel[j])
			{
				color(j,3-c); // color the opposite color 1<->2
			}
		}
	}
}
 
void dye()
{
	int i,j;
	F[N+1]=INF;
	for (i=N;i>=1;i--)
	{
		F[i]=S[i];
		if (F[i+1]<F[i])
			F[i]=F[i+1];
	}
	for (i=1;i<=N-1;i++)
	{
		for (j=i+1;j<=N;j++)
		{
			if (S[i]<S[j] && F[j+1]<S[i])
			{
				adjm[i][j]=adjm[j][i]=true;
			}
		}
	}
	for (i=1;i<=N;i++)
	{
		if (!bel[i])
		{
			color(i,1);
		}
	}
}
 
void solve()
{
	int i,should=1,s;
	for (i=1;i<=N;i++)
	{
		s=bel[i];
		if (s==1)
		{
			T[1].ins(S[i]);
			printf("a ");
		}
		else
		{
			T[2].ins(S[i]);
			printf("c ");
		}
		while (T[1].tp()==should || T[2].tp()==should)
		{
			if (T[1].tp()==should)
			{
				T[1].pop();
				printf("b");
				if (should!=N)
					printf(" ");
				should++;
			}
			else
			{
				T[2].pop();
				printf("d");
				if (should!=N)
					printf(" ");
				should++;
			}
		}
	}
}
 
int main()
{
	init();
	dye();
	solve();
	return 0;
}