Problem D
Ant Typing
Consider a configurable keyboard where keys can be moved about. An ant is walking on the top row of this keyboard and needs to type a numeric string. The ant starts on the leftmost key of the top row, which contains $9$ keys, some permutation of the digits from $1$ to $9$. On a given second, the ant can perform one of three operations:
-
Stay on that key. The digit corresponding to that key will be entered.
-
Move one key to the left. This can only happen if the ant is not on the leftmost key.
-
Move one key to the right. This can only happen if the ant is not on the rightmost key.
Compute the minimum number of seconds needed for the ant to type out the given numeric string, over all possible numeric key permutations.
Input
The single line of input contains a single string $s$ ($1 \le |s| \le 10^5$) consisting only of numeric digit characters from $1$ to $9$. This is the numeric string that the ant needs to type.
Output
Output a single integer, which is the minimum number of seconds needed for the ant to type out the given numeric string, over all possible numeric key permutations.
| Sample Input 1 | Sample Output 1 |
|---|---|
78432579 |
20 |
