当前没有测试数据。

题目描述

小 $A$ 在一家物流公司负责管理货仓的编号系统。每个货仓都有一个唯一的编号，用一个正整数 $N$ 表示。为了提高货物配送效率，公司决定调整部分货仓的编号。

具体方法是将编号 $N$ 的各位数字重新排列，生成一个新的正整数，要求这个新编号严格小于原来的编号 $N$，并且在所有满足条件的重排编号中，数值最大。

如果无法找到比原编号小的重排数字，则该货仓的编号保持不变，小 $A$ 记录 $-1$ 表示无需调整。

你的任务是帮助小 $A$ 计算出符合要求的最大重排编号，或者在无法调整时输出 $-1$。

输入格式

输入一个正整数 $N$，表示货仓的原编号。

输出格式

输出一个正整数，表示所有严格小于 $N$ 的重排编号中最大的那个，如果不存在这样的重排编号，则输出 $-1$。

样例 #1

输入

312

输出

231

样例 #2

输入

789012

输出

782910

样例 #3

输入

13589

输出

-1

样例说明

样例 1 说明

对于样例 $1$，货仓编号 $312$ 的所有重排数字中小于 $312$ 的有 $231$、$213$、$132$、$123$，其中最大的是 $231$，因此输出 $231$。

数据范围

对于所有测试数据，保证：$1 \le N \le 10^{18}$。

测试点	$N$	特殊性质
$1 \sim 3$	$1 \le N \le 10^8$	无
$4 \sim 6$	$1 \le N \le 10^{18}$	A
$7 \sim 20$		无

特殊性质A：保证 $N$ 的各个位依次递增，如：$123$。