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.

-----Examples-----
Sample Input 1:
10
Sample Output 1:
10

Sample Input 2:
55
Sample Output 2:
55

Sample Input 3:
101
Sample Output 3:
-1

Sample Input 4:
1234321
Sample Output 4:
94708

Source: kattis | Difficulty: HARD
Tags: String algorithms


Solutions: