Hide

Problem D
Hill Number

A Hill Number is a positive integer, the digits of which possibly rise and then possibly fall, but never fall and then rise. For example:

12321 is a hill number.
12223 is a hill number.
33322111 is a hill number.
1232321 is not a hill number.

Given a positive integer, if it is a hill number, print the number of positive hill numbers less than or equal to it. If it is not a hill number, print -1.

Input

Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. Each test case will consist of a single integer $n$ ($1 \le n \le 10^{18}$).

Output

Output a single line with a single integer. If the input is a hill number, then output the number of hill numbers less than or equal to it. If the input is not a hill number, then output -1.

Sample Input 1 Sample Output 1
10
10
Sample Input 2 Sample Output 2
55
55
Sample Input 3 Sample Output 3
101
-1
Sample Input 4 Sample Output 4
1234321
94708
Sample Input 5 Sample Output 5
1000
715

Please log in to submit a solution to this problem

Log in