排列 $p = \langle p_1, p_2, \dots, p_n \rangle$ 中的逆序对是指满足 $i < j$ 且 $p_i > p_j$ 的整数对 $(i, j)$。

考虑正整数的字典序。在这种排序方式下，整数被视为数字字符串进行字典序比较。例如，628 排在 7 之前，239 排在 271 之前，42 排在 427 之前。

给定一个正整数 $n$。将 $1$ 到 $n$ 之间的所有整数按字典序排序，我们将得到一个长度为 $n$ 的排列 $p$，其中 $p_1$ 是 $1$ 到 $n$ 之间字典序最小的整数（实际上对于任何 $n$，$p_1 = 1$），$p_2$ 是字典序第二小的整数，以此类推。

请问排列 $p$ 包含多少个逆序对？

输入格式

输入仅一行，包含一个不含前导零的正整数 $n$。

$n$ 的取值范围在 $1$ 到 $10^{250\,000} - 1$ 之间（包含边界）。也就是说，$n$ 最多包含 $250\,000$ 位数字。

输出格式

输出一个不含前导零的整数，表示 $p$ 中的逆序对数量。

样例

样例输入 1

11

样例输出 1

16

样例输入 2

427

样例输出 2

26576

说明

事实上，在第一个样例中，$p = \langle 1, 10, 11, 2, 3, 4, 5, 6, 7, 8, 9 \rangle$，它包含 16 个逆序对。