내림차순 수열

문제

어떤 양의 정수의 각 자릿수가 왼쪽에서 오른쪽으로 갈수록 단조 감소할 때, 이를 "감소하는 수"라고 부른다. 예를 들어 321, 951, 10은 감소하는 수이지만, 322, 121은 아니다. 한 자릿수인 0부터 9까지도 감소하는 수로 간주한다.

감소하는 수를 0번째부터 시작하여 오름차순으로 나열했을 때, N번째 감소하는 수를 구하라. 감소하는 수는 0부터 9까지 한 자릿수 10개, 두 자릿수 45개, ..., 최대 10자릿수 9876543210까지 총 1023개만 존재한다.

입력

첫째 줄에 구하고자 하는 감소하는 수의 순서 N이 주어진다.

출력

N번째 감소하는 수를 출력하라. N번째 감소하는 수가 존재하지 않으면 -1을 출력한다.

제한

• 0 ≤ N ≤ 1000000

입출력 예시

입력 1

18

출력 1

42

입력 2

0

출력 2

0

입력 3

1000000

출력 3

-1

설명: 감소하는 수를 작은 순서대로 나열하면 0, 1, 2, ..., 9, 10, 20, 21, 30, 31, 32, 40, 41, 42, ... 이다. 18번째 수는 42이다.