Decreasing Numbers

Time limit2sMemory limit128 MB

Summary

Given N, output the N-th smallest number whose decimal digits strictly decrease left to right, or -1 if it does not exist.

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

Problem

A nonnegative integer is called a decreasing number if, when written in decimal notation, each digit is strictly smaller than the digit immediately to its left. For example, 321 and 950 are decreasing numbers, while 322 and 958 are not.

Given a positive integer N, print the N-th smallest decreasing number. The smallest decreasing number is 0, so it is the 1st one. If the N-th decreasing number does not exist, print -1.

Input

The first line contains a positive integer N. N is at most 1,000,000.

Output

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

Examples3

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