Best Cow Line

Farmer John has N cows (where \(1 \leq N \leq 5 \times 10^5\)) participating in the annual "All-America Farm Championship". In this contest, each contestant must line up their cows and have them walk past the judges in order. The new registration rule collects the first letter of each cow's name from the original order, and then sorts the resulting strings in lexicographical (dictionary) order to determine the order of appearance.

Farmer John, pressed for time, wants his cows to appear as early as possible. He is allowed to rearrange the cow line using the following procedure: In each step, he takes either the first cow or the last cow from the original line and appends her to the end of a new line. This process is repeated until all cows have been moved to the new line.

Your task is to help Farmer John determine the lexicographically smallest possible string (formed by the first letters of the cow names) that can be obtained using this method.

inputFormat

The first line contains an integer \(N\) (\(1 \leq N \leq 5 \times 10^5\)), representing the number of cows. The following \(N\) lines each contain a single uppercase letter, representing the first letter of a cow's name in the original order.

outputFormat

Output a single line containing the lexicographically smallest string obtainable by repeatedly taking either the first or the last letter from the remaining sequence.

sample

4
A
C
D
B

ABCD