시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB41125.000%

문제

An inversion in permutation $p = \langle p_1, p_2, \ldots, p_n \rangle$ is a pair of integers $(i, j)$ such that $i < j$ and $p_i > p_j$.

Consider a lexicographical order on positive integers. Under this ordering, integers are compared lexicographically as strings of digits. For example, 628 comes before 7, 239 comes before 271, and 42 comes before 427.

You are given a single positive integer $n$. Let's sort all integers from 1 to $n$, inclusive, in lexicographical order. We'll get a permutation $p$ of length $n$, where $p_1$ is the lexicographically smallest integer between 1 and $n$ (actually, $p_1 = 1$ for any $n$), $p_2$ is the second smallest one, and so on.

How many inversions does $p$ contain?

입력

The only line of the input contains a single positive integer $n$ without leading zeroes.

The value of $n$ will be between 1 and $10^{250\,000} - 1$, inclusive. That is, $n$ will consist of no more than $250\,000$ decimal digits.

출력

Output a single integer without leading zeroes --- the number of inversions in $p$.

예제 입력 1

11

예제 출력 1

16

예제 입력 2

427

예제 출력 2

26576

힌트

Indeed, in the first example test case, $p = \langle 1, 10, 11, 2, 3, 4, 5, 6, 7, 8, 9 \rangle$ contains 16 inversions.