Next Permutation

Given an integer sequence P of length \( n \), your task is to compute its next lexicographically greater permutation. If such a permutation does not exist, rearrange it into its lowest possible order (i.e., sorted in ascending order).

The sequence can be expressed as \( P = [p_1, p_2, \dots, p_n] \). The next permutation is the next sequence in the lexicographic order. For example, if \( P = [1, 2, 3] \), the next permutation is \( [1, 3, 2] \). However, if \( P = [3, 2, 1] \), then there is no permutation greater than \( P \) and the answer is \( [1, 2, 3] \).

inputFormat

The first line contains an integer n representing the number of elements in the permutation. The second line contains n space-separated integers representing the permutation.

outputFormat

Output the next permutation as a single line of space-separated integers.

3
1 2 3

1 3 2