Given an integer array arr, modify arr in-place to its next lexicographically greater permutation. If such permutation does not exist (i.e., arr is sorted in descending order), rearrange arr to the lowest possible order (sorted ascending). The operation must be performed in-place with constant extra memory.
Example 1
Input: [4,1,2]
Output: [4,2,1]
Explanation: The next permutation after [4,1,2] is [4,2,1].
Example 2
Input: [2,2,1]
Output: [1,2,2]
Explanation: No lexicographically greater permutation exists, so return lowest order.
Example 3
Input: [1,5,3]
Output: [3,1,5]
Explanation: The next permutation after [1,5,3] is [3,1,5].
Constraints
Case 1
Input: [1,3,4,2]
Expected: [1,4,2,3]
Case 2
Input: [5,4,3,2,1]
Expected: [1,2,3,4,5]
Case 3
Input: [2,1,3]
Expected: [2,3,1]
Case 4
Input: [1,1,1]
Expected: [1,1,1]
Case 5
Input: [0,2,1]
Expected: [1,0,2]