Decreasing Number

Time limit1sMemory limit512 MB

Summary

Given N, find the N-th smallest non-negative integer whose digits strictly decrease from left to right, or output -1 if none exists.

Level: Medium6 of 10
Topics: Combinatorics, Greedy, Math, Backtracking
Solved: No attempts yet

Problem

A non-negative integer is called a decreasing number if each digit is strictly smaller than the digit immediately to its left, from the most significant digit to the least significant digit. For example, 321 and 950 are decreasing numbers, but 322 and 958 are not.

Given N, print the N-th decreasing number when all decreasing numbers are sorted in increasing order. The number 0 is the 0-th decreasing number, and 1 is the 1st decreasing number. If the N-th decreasing number does not exist, print -1.

Input

The first line contains N. N is either 0 or a natural number not greater than 1,000,000.

Output

Print the N-th decreasing number on the first line. If it does not exist, print -1.

Examples3

Example 1
Input
```
18
```
Expected output
```
42
```
Example 2
Input
```
0
```
Expected output
```
0
```
Example 3
Input
```
500000
```
Expected output
```
-1
```