Next Permutation

Arrange the numbers into the next greater permutation in dictionary (lexicographic) order. If the array is already the greatest arrangement (non-increasing), wrap around to the smallest one (sorted ascending).

For example, the permutations of 1 2 3 in order are 123, 132, 213, 231, 312, 321, so the next permutation of 1 3 2 is 2 1 3, and the next of 3 2 1 is 1 2 3.

Input:

• line 1: n
• line 2: n integers (they may repeat)

Output: the next permutation on one line.

Constraints: 1 ≤ n ≤ 10⁵, 0 ≤ a[i] ≤ 100.

Think about it: from the right, find the first position where the sequence goes down; swap it with the next-larger value to its right, then reverse the tail.