Next Lexicographical Permutation

Given a string S of length N, the task is to find its next lexicographical permutation. If no larger permutation exists, output the smallest permutation (i.e., the characters sorted in ascending order).

For example:

• For S = abc, the next permutation is acb.
• For S = cba, no larger permutation exists, so the output should be abc.

The solution should read input from standard input (stdin) and write the result to standard output (stdout). The input consists of an integer N in the first line followed by the string S in the next line.

Note: All formulas below are rendered in LaTeX format. For example, the condition to find the pivot element can be written as:

\( S[i] < S[i+1] \)

inputFormat

The input is given via standard input. The first line contains an integer \(N\), representing the length of the string \(S\). The second line contains the string \(S\), consisting of lowercase letters.

outputFormat

Output the next lexicographical permutation of \(S\) to standard output. If no permutation greater than \(S\) exists, output the smallest permutation (i.e., sorted in ascending order).

3
abc

acb