登录/注册
336. 上一个排列
时间限制: C/C++ 1000 ms | 其他语言 2000 ms
内存限制: C/C++ 64 MB | 其他语言 128 MB
尝试次数: 63 | 通过次数: 49
尝试人数: 43 | 通过人数: 40
标签: STL
难度: 简单+
0
1

给定一个整数序列,可能包含重复元素。输出它的上一个排列。如果不存在上一个排列,则输出 -

所谓上一个排列,是指字典序比它小但最接近它的排列,例如:

  • 1 1 3 21 \ 1 \ 3 \ 2 的上一个排列是 1 1 2 31 \ 1 \ 2 \ 3
  • 1 2 31 \ 2 \ 3 没有上一个排列,它的字典序最小

输入

  • 多组测试数据,以 EOF 介绍
  • 每组测试数据:
    • 第一行一个整数 n(1n8)n(1 \leq n \leq 8)
    • 第二行 nn 个有符号 3232 位整数

输出

  • 每组测试数据输出一行,表示上一个排列
  • 不存在则输出 -

提示

  • 最后一个元素的后面不要输出空格
样例 1
输入
4
1 1 3 2
3
1 2 3
输出
1 1 2 3
-