Next Permutation

MediumArrays

Rearrange the numbers into the lexicographically next greater permutation. If no greater permutation exists (the array is in descending order), wrap around to the smallest (ascending) permutation. Do it in place.

Input format (stdin): the first line has n. The second line has n integers. Output the next permutation, space separated.

Examples

Input: 3 1 2 3

Output: 1 3 2

Input: 3 3 2 1

Output: 1 2 3

Already the largest, so wrap to smallest.

Input: 4 1 1 5 0

Output: 1 5 0 1

Constraints

1 <= n <= 100
0 <= nums[i] <= 100

Sheets

Love Babbar 450Striver A2Z

next-permutation.cpp3 sample tests

Loading editor

Test results

Run the sample tests to check your solution against expected output.

Custom input (stdin)

Output

Run your code to see its output.