Next Permutation

You are given a sequence of integers. Your task is to rearrange the numbers into the lexicographically next greater permutation of numbers. If such an arrangement is not possible, you must rearrange it to the lowest possible order (i.e. sorted in ascending order).

The rearrangement must be performed in-place and use only constant extra memory.

Note: The permutation is compared lexicographically. For example, for the array \( a = [a_1, a_2, \dots, a_n] \), its lexicographic successor is the next sequence \( b = [b_1, b_2, \dots, b_n] \) such that \( a < b \) in dictionary order. If no such \( b \) exists, output the sequence sorted in ascending order.

For example:

Input:  1 2 3
Output: 1 3 2
Input:  3 2 1
Output: 1 2 3

</p>

inputFormat

The input is given from standard input (stdin) and has the following format:

• The first line contains an integer \( n \) representing the number of elements in the array.
• The second line contains \( n \) space-separated integers representing the array.

outputFormat

Output to standard output (stdout) the resulting array after performing the next permutation operation. The numbers should be printed in a single line separated by a single space.

## sample

3
1 2 3

1 3 2

</p>