#1182. [STEMA.CPP.23403-5] 数字重组

[STEMA.CPP.23403-5] 数字重组

描述

编程实现:给定一个正整数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。

输入输出格式

输入

输入一个正整数 n (1n<263 1 ≤ n < 2^{63} )

输出

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

样例

312
231