Lexicographically Smallest String Through Reversals

You are given a string s of length n. You are allowed to reverse any segment of the string any number of times. Prove that by doing this, you can always obtain the lexicographically smallest string possible, which is equivalent to the sorted version of s.

In other words, the answer is the string with its characters arranged in non-decreasing order. Formally, if we denote the sorted string as \(\mathrm{Sorted}(s)\), then the required output is \(\mathrm{Sorted}(s)\).

Example:

• For n = 4 and s = "dcba", the lexicographically smallest string is "abcd".

inputFormat

The input consists of two lines. The first line contains a single integer n (the length of the string). The second line contains the string s consisting of lowercase English letters.

outputFormat

Output a single line: the lexicographically smallest string obtainable, which is just the sorted version of the input string.

1
a

a