String Construction 2

You are given a string $S$ made up of $N$ characters. Using the characters of this string, you want to build a new string $T$.

$T$ is built by repeatedly applying one of the following two operations until $S$ becomes empty:

• Remove the first (leftmost) character of $S$ and append it to the end of $T$.
• Remove the last (rightmost) character of $S$ and append it to the end of $T$.

In other words, at each step you take one character from either the front or the back of the remaining $S$ and append it to the end of $T$. Among all strings $T$ that can be built this way, print the lexicographically smallest one.

The first line contains $N$, the length of the string $S$ ($N \le 30000$).

Each of the next $N$ lines contains one character of $S$, given in order.

Print the lexicographically smallest string $T$ that can be built.

Print at most 80 characters per line; that is, start a new line after every 80 characters.

For example, consider $S=$ ACDBCB. At each step, compare the first and last characters of the remaining $S$ and append the character from the side that yields the smaller string. If the two characters are equal, move inward one character at a time and compare at the first position where they differ, choosing the smaller side.

• A < B, so append the front A. (remaining $S=$ CDBCB, $T=$ A)
• B < C, so append the back B. (remaining $S=$ CDBC, $T=$ AB)
• both ends are C, so compare the inner D and B; the back side is smaller, so append the back C. (remaining $S=$ CDB, $T=$ ABC)
• B < C, so append the back B. (remaining $S=$ CD, $T=$ ABCB)
• C < D, so append the front C. (remaining $S=$ D, $T=$ ABCBC)
• append the remaining D. (remaining $S$ empty, $T=$ ABCBCD)

So the answer is ABCBCD.