Hide

Problem M
Champernowne Verification

The $k^{\text {th}}$ Champernowne word is obtained by writing down the first $k$ positive integers and concatenating them together. For example, the $10^{\text {th}}$ Champernowne word is $12345678910$.

Given a positive integer $n$, determine if it is a Champernowne word, and if so, which word.

Input

The first line contains a single integer, $n$ ($1 \le n \le 10^9$). $n$ will not have leading zeroes.

Output

If $n$ is the $k^{\text {th}}$ Champernowne word, output $k$. Otherwise, output $-1$.

Sample Input 1 Sample Output 1
123456789
9
Sample Input 2 Sample Output 2
1000000000
-1
Sample Input 3 Sample Output 3
11
-1
Sample Input 4 Sample Output 4
1324
-1

Please log in to submit a solution to this problem

Log in