Inversions in Lexicographical Order

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 as strings of digits. For example, 628 comes before 7, 239 comes before 271, and 42 comes before 427.

You are given a positive integer $n$. Sort all integers from 1 to $n$, inclusive, in lexicographical order. This gives a permutation $p$ of length $n$, where $p_1$ is the smallest integer between 1 and $n$ in this order (which is always 1), $p_2$ is the second smallest, 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$ is between 1 and $10^{250\,000} - 1$, inclusive, so $n$ has at most 250000 decimal digits.

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

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