题目描述

若给出一个数 n ,则 1 ~ n 这 n 个数可组成n!种排列,把这些排列按字典序（按照字母顺序，或者数字小大顺序，由小到大的形成序列）列出。

若给出其中的一个排列，求这个排列的下一个排列。

输入格式

第一行输入数字n，表示后面队列由1~n n个数组成 

第二行输入当前的一个排列

输出格式

求出此排列的下一个排列

样例数据

input

4
3 2 4 1

output

3 4 1 2