Problem Description

Tom is studying an interesting sorting problem. As shown in the figure, using two stacks \( S_1 \) and \( S_2 \), Tom aims to sort an input sequence in ascending order through the following four operations:

• Operation a: Push the first element into stack \( S_1 \).
• Operation b: Pop the top element from stack \( S_1 \) to the output sequence.
• Operation c: Push the first element into stack \( S_2 \).
• Operation d: Pop the top element from stack \( S_2 \) to the output sequence.

If a permutation \( P \) of \( 1 \) to \( n \) can be sorted into the sequence \( (1, 2, \cdots, n-1, n) \) through a series of valid operations, Tom calls \( P \) a "double stack sortable permutation". For example, \( (1, 3, 2, 4) \) is a "double stack sortable sequence", while \( (2, 3, 4, 1) \) is not. The figure below illustrates an operation sequence to sort \( (1, 3, 2, 4) \): a, c, c, b, a, d, d, b.

There might be multiple valid operation sequences. For the example \( (1, 3, 2, 4) \), a, b, a, a, b, b, a, b is another feasible sequence. Tom wants to know the lexicographically smallest operation sequence.

Input Format

The first line contains an integer \( n \).

The second line contains \( n \) positive integers separated by spaces, forming a permutation of \( 1 \) to \( n \).

Output Format

Output a single line. If the input permutation is not "double stack sortable", output 0.

Otherwise, output the lexicographically smallest operation sequence, with each operation separated by a space and no space at the end of the line.

Sample Input and Output

Sample Input #1

4
1 3 2 4

Sample Output #1

a b a a b b a b

Sample Input #2

4
2 3 4 1

Sample Output #2

0

Sample Input #3

3
2 3 1

Sample Output #3

a c a b b d

Notes

30% of the data satisfies: \( n \le 10 \).

50% of the data satisfies: \( n \le 50 \).

100% of the data satisfies: \( n \le 1000 \).

This problem was enhanced by SSerxhs on June 17, 2021. Hack data is separated into a subtask to prevent confusion.

This is the fourth question from the NOIP2008 Senior Group.

见题面 Input 部分

见题面 Output 部分