Double Stack Sorting and Lexicographically Minimal Operation Sequence

Tom is studying an interesting sorting problem. Given a permutation of the integers from \(1\) to \(n\), Tom wants to sort it in ascending order by employing two stacks \(S_1\) and \(S_2\) together with the following four operations:

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

If a permutation \(P\) of \(1\) to \(n\) can be sorted to produce the ascending sequence \(1,2,\dots,n\) via a sequence of legal operations, then \(P\) is called a double stack sortable permutation. For example, the permutation (1, 3, 2, 4) is double stack sortable while (2, 3, 4, 1) is not.

Multiple valid sequences of operations may exist for the same permutation. For instance, for (1,3,2,4), two valid sequences are:

1. a, c, c, b, a, d, d, b
2. a, b, a, a, b, b, a, b

Your task is to determine, for a given permutation, the lexicographically smallest (with the order \(a < b < c < d\)) sequence of operations that sorts the permutation. If no valid sequence exists, output No solution.

Note: When performing a pop operation (b or d), the element popped must be equal to the next required number in ascending order. In other words, if you have already output \(1,2,\dots,k\), then the popped element must equal \(k+1\).

inputFormat

The first line contains a positive integer \(n\) (the size of the permutation). The second line contains \(n\) space-separated integers representing a permutation of \(1\) to \(n\).

outputFormat

If the permutation is double stack sortable, output the lexicographically smallest sequence of operations (a string consisting of letters a, b, c, d) which sorts the permutation; otherwise, output No solution.

sample

4
1 3 2 4

ababbbab