题目描述

给定一个正整数 $n$，请将 $n$ 中的每位数字重新排列并组成一个新数，要求新数的值要小于 $n$，请找出所有符合要求的新数中最大的那个正整数，如果不存在这样的正整数，则输出 $-1$。

例1：$n=312$，$312$ 中每位上的数字依次是 $3、1、2$，重新排列组成的新数有 $321、231、213、132、123$，新数中小于 $312$ 的有 $231、213、132、123$，其中符合要求的最大正整数是 $231$；

例2：$n=123$，$123$ 中每位上的数字依次是 $1、2、3$，重新排列组成的新数有 $312、321、231、213、132$，新数中不存在小于 $123$ 的正整数，故输出 $-1$。

「注意」 要求每位数字重新排列并组成的新数不能含有前导 $0$，求出在此前提下，最大的小于 $n$ 的正整数。如果不存在，输出 $-1$。

例如，如果输入 $108$，那么比 $108$ 小的整数有 $018$ 和 $081$，但是他们都含有前导 $0$，不满足条件，因此输出 $-1$。

输入格式

输入一个正整数 $n (1≤ n \lt 2​^{63}​)$。

输出格式

输出一个正整数，表示符合要求的最大正整数。

312

231

108

-1