题目描述

给定一个正整数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（1 ≦ n ≦ 2^63）

输出描述

输出一个整数，表示符合要求的最大正整数，如不存在，则输出-1

样例数据1

输入

312

输出

231

样例数据2

输入

123

输出

-1

程序运行限制

时间限制：1000ms、内存限制：64MB