Next Permutation

Given a sequence of integers, your task is to compute its next lexicographical permutation. If no such permutation exists (i.e. the sequence is in descending order), output the sequence in ascending order instead.

In other words, for a sequence \(a_1, a_2, \dots, a_n\), find the next permutation that would appear if all permutations were listed in sorted order. If the sequence is the largest possible permutation, then rearrange the numbers to the smallest possible order.

You are required to use the standard input/output streams for this problem.

inputFormat

The input consists of two lines.

• The first line contains an integer \(n\) (1 \(\leq\) n \(\leq\) 10⁵), representing the number of integers in the sequence.
• The second line contains \(n\) space-separated integers.

outputFormat

Output a single line with \(n\) space-separated integers representing the next permutation of the input sequence. If the input sequence is the largest permutation, output the sequence sorted in ascending order.

3
1 2 3

1 3 2