You happened to find a queue of lowercase latin characters in the mailbox. You decide you want to do something productive with these characters. As such, you will try to build a string. For each character in the queue, in order, you will either prepend or append the character to a new string, and then remove the character from the queue. Recall that a queue is First-In First-Out (FIFO), meaning that the character at the front of the queue (the first character) is removed first, second character second, etc.
Given the queue of characters, what is the lexicographically smallest string that can be built?
Input Specification
The first line will contain the integer , the number of characters in the queue.
The second line will contain lowercase latin characters concatenated together. The first character will be the first character in the queue, second character the second character in the queue, etc.
Output Specification
Output the lexicographically smallest string that can be built. This string should consist of exactly characters.
Subtasks
For 6/15 of the points,
Sample Input
5
bzbsa
Sample Output
abbzs
Comments