50 - 下一个排列

JM现在有1~n共n个数字的一个排列,JM想知道这个排列的下一个排列是哪个?

输入

输入第一行包含一个整数n,2 <= n <= 3000。

输入第二行包含一行n个整数ai。

输出

输出该排列的下一个排列。

当然,如果已经是最后一个排列了,则下一个排列为第一个排列(例如样例2)。

样例

输入

3
1 2 3

输出

1 3 2

输入

4
4 3 2 1

输出

1 2 3 4
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题