Next Permutation

Given a sequence of n integers a₁, a₂, \ldots, a_n representing a permutation, your task is to rearrange the numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible, it must be rearranged as the lowest possible order (i.e. sorted in ascending order).

The next permutation of a sequence is defined as the next sequence that is greater than the current one when compared lexicographically. Formally, a permutation P = (p₁, p₂, \ldots, p_n) is considered lexicographically smaller than a permutation Q = (q₁, q₂, \ldots, q_n) if for some index i (with \(1 \le i \le n\)) we have:

[ p_{1} = q_{1},; p_{2} = q_{2},; \dots, ; p_{i-1} = q_{i-1}\quad \text{and}\quad p_{i} < q_{i}. ]

If no lexicographically larger permutation exists, the sequence must be rearranged to the smallest possible order.

inputFormat

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

outputFormat

Output the lexicographically next permutation as a sequence of n space-separated integers on a single line. If no next permutation exists, output the smallest permutation (i.e. the numbers in ascending order).

3
1 2 3

1 3 2