下一个排列

题目描述

实现一个函数，用于计算给定数字序列的下一个排列。

下一个排列是指，将该数字序列重新排列成一个在字典序上严格大于当前排列的新排列。在所有可能的、大于当前排列的新排列中，这个“下一个排列”是最小的那一个。

如果不存在比当前排列更大的排列（即当前排列已是所有可能排列中字典序最大的），则应将数字序列重新排列成字典序最小的排列（即升序排列）。

要求：

• 必须原地修改输入的数组。
• 只允许使用常数级别的额外空间。

输入格式

第一行包含一个整数 $n$，表示数组的长度。

第二行包含 $n$ 个整数 $nums_1, nums_2, \dots, nums_n$，表示当前的排列。

输出格式

输出一行 $n$ 个整数，表示计算出的下一个排列，数字之间用空格分隔。

样例

样例输入 1

3
1 2 3

样例输出 1

1 3 2

样例输入 2

3
3 2 1

样例输出 2

1 2 3

样例输入 3

3
1 1 5

样例输出 3

1 5 1

提示

数据范围与约定

对于 $100\%$ 的数据，保证：

• $1 \le n \le 100$
• $0 \le nums_i \le 100$