Next Lexicographical Permutation

Given a permutation of n integers, your task is to compute its next lexicographical permutation. That is, rearrange the numbers into the lexicographically next greater permutation of numbers.

If such permutation does not exist (i.e., the permutation is the highest possible), then output the permutation sorted in ascending order.

Recall that a permutation A is lexicographically smaller than a permutation B if at the first position where they differ, the sequence A has a smaller element than the corresponding element in B. In mathematical notation, if the permutation is a_1, a_2, ..., a_n, and no index i exists such that a_i < a_{i+1}, then the permutation is the highest possible. Otherwise, the next permutation is defined as the smallest permutation that is greater than the given permutation.

You can use the following procedure:

1. Find the largest index i such that \(a_i < a_{i+1}\).
2. Find the largest index j greater than i such that \(a_j > a_i\).
3. Swap \(a_i\) and \(a_j\).
4. Reverse the sequence from \(a_{i+1}\) to \(a_n\).

inputFormat

The first line of input contains an integer n, the number of elements in the permutation.

The second line contains n space-separated integers representing the current permutation.

outputFormat

Output the next lexicographical permutation as n space-separated integers on a single line. If no such permutation exists, output the sorted permutation in ascending order.

6
1 2 3 6 5 4

1 2 4 3 5 6