시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 512 MB4010832.000%

문제

인도 수학자 Kaprekar는 Kaprekar's routine이라는 반복 알고리즘을 고안했다. 이 알고리즘의 한 단계는 $N$자리 수에 대해서 각 자리의 숫자를 재배열하여 만들 수 있는 가장 큰 수와 가장 작은 수의 차이를 계산하는 것이다. 단, 가장 작은 수를 구할 때 맨 앞에 $0$이 오는 것을 허용한다.

이때, 어떤 수는 한 단계를 거쳐도 처음 수와 같은 결괏값을 얻게 된다. 한 예시로 $6174$가 있다. $6174$를 재배열하여 만들 수 있는 가장 큰 수는 $7641$이고 가장 작은 수는 $1467$이다. $7641$과 $1467$의 차이는 $6174$가 되어, 처음 수와 같아진다.

Kaprekar's routine을 알게 된 파이시스는 위 단계가 너무 단조롭다고 생각했다. 그래서 자신이 좋아하는 숫자 $2$를 추가하고 싫어하는 숫자 $0$을 제거하여 Kapr2kar's r0utine이라는 새 반복 알고리즘을 만들었다. Kapr2kar's r0utine의 한 단계는 숫자 $0$이 포함되지 않은 $N$자리 수에 대해서 각 자리의 숫자를 재배열하여 만들 수 있는 $2$번째로 큰 수와 $2$번째로 작은 수의 차이를 계산하는 것이다. 당연히, $1$이나 $9999$와 같이 모든 자리 숫자가 같은 수는 $2$번째로 큰 수나 $2$번째로 작은 수가 존재하지 않으므로 고려하지 않는다.

파이시스는 Kapr2kar's r0utine에서도 한 단계를 거쳤을 때 처음과 같은 결괏값을 얻는 수가 있는지 궁금해졌다. 그를 도와주는 프로그램을 작성하자.

입력

첫째 줄에 구하려는 수가 몇 자리 수인지를 나타내는 양의 정수 $N$이 주어진다. ($2\leq N\leq 10^5$)

출력

첫째 줄에 Kapr2kar's r0utine의 한 단계를 거쳤을 때 처음과 같은 결괏값을 얻는 $N$자리 수를 아무거나 하나 출력한다.

단, 조건을 만족하는 수가 존재하지 않는다면 $-1$을 출력한다.

예제 입력 1

3

예제 출력 1

-1

예제 입력 2

5

예제 출력 2

73926

$73926$의 각 자릿수를 재배열하여 만들 수 있는 $2$번째로 큰 수는 $97623$이고, $2$번째로 작은 수는 $23697$이다. $97623$과 $23697$의 차이는 $73926$이 되어, 처음 수와 같아진다. 따라서 $73926$은 Kapr2kar's r0utine의 한 단계를 거쳤을 때 처음과 같은 결괏값을 얻는 $5$자리 수이다.

출처