Mock CCC '20 Contest 2 S2 - 4D BBST on a DP

View as PDF

Submit solution

Points: 5 (partial)
Time limit: 0.5s
Memory limit: 128M

Author:
Problem type

You happened to find a queue of N 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 N (1 \le N \le 10^5), the number of characters in the queue.

The second line will contain N 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 N characters.

Subtasks

For 6/15 of the points, N \le 10

Sample Input

5
bzbsa

Sample Output

abbzs

Comments

There are no comments at the moment.