사전식 순서의 역전 개수

순열 $p = \langle p_1, p_2, \ldots, p_n \rangle$에서 역전(inversion)이란 $i < j$이고 $p_i > p_j$인 정수 쌍 $(i, j)$를 말한다.

양의 정수에 대한 사전식 순서를 생각하자. 이 순서에서는 정수를 십진수 숫자 문자열로 보고 사전순으로 비교한다. 예를 들어 628은 7보다 앞에 오고, 239는 271보다 앞에 오며, 42는 427보다 앞에 온다.

양의 정수 $n$이 주어진다. 1부터 $n$까지의 모든 정수를 사전식 순서로 정렬하자. 그러면 길이가 $n$인 순열 $p$를 얻는다. 여기서 $p_1$은 1부터 $n$까지의 정수 중 사전식 순서가 가장 앞선 수이고(항상 1이다), $p_2$는 두 번째로 앞선 수이며, 이런 식으로 이어진다.

$p$에는 역전이 몇 개 있는가?

입력은 한 줄이며, 앞자리에 0이 없는 양의 정수 $n$이 하나 주어진다. $n$의 값은 1 이상 $10^{250\,000} - 1$ 이하이다. 즉 $n$은 최대 250000자리의 십진수이다.

$p$의 역전 개수를 앞자리에 0이 없는 정수 하나로 출력한다.

첫 번째 테스트에서 $p = \langle 1, 10, 11, 2, 3, 4, 5, 6, 7, 8, 9 \rangle$는 역전을 16개 가진다.