Rearrange the numbers of the array into the next permutation that is lexicographically greater than the current arrangement. If the array is already the lexicographically largest permutation, wrap around to the smallest (sorted ascending) permutation.
Permutations are compared element by element as sequences.
Input format
Line 1: an integer n.
Line 2: n space-separated integers (may contain duplicates; present whenever n >= 1).
Output format
One line: the next permutation, space-separated.
Constraints
- 1 <= n <= 100000
- -1000000000 <= each value <= 1000000000