Writing Consecutive Numbers 3

Time limit2sMemory limit128 MB

Summary

Given N, find the earliest 1-based index where the digit-string of N occurs inside the concatenation of integers 1 through N.

Level: Medium4 of 10
Topics: String matching, String, Brute force
Solved: No attempts yet

Problem

Write the integers from 1 through N in order to make one string.

1234567891011121314151617181920212223...

Find the first position where the decimal representation of N appears in this string. The number N always appears at the end because the string includes N itself, but it may also appear earlier as part of other numbers or across the boundary between two adjacent numbers.

For N = 151, the substring 151 begins at the 20th digit.

1234567891011121314151617181920212223...

Given N, write a program that prints the first 1-based position where N appears.

Input

The first line contains an integer N (1 <= N <= 100,000).

Output

Print the first position where the decimal representation of N appears in the string made by writing the integers from 1 through N. Count the first digit as position 1.

Examples3

Example 1
Input
```
15
```
Expected output
```
20
```
Example 2
Input
```
34
```
Expected output
```
3
```
Example 3
Input
```
142
```
Expected output
```
73
```