Ant Typing

Time limit1sMemory limit512 MB

Summary

Choose an arrangement of the digits 1 to 9 on nine keys so an ant walking left or right types a given digit string in the fewest seconds.

Level: Medium6 of 10
Topics: Dynamic programming, Greedy, Math, Implementation
Solved: No attempts yet

Problem

Consider a configurable keyboard whose keys can be rearranged. An ant walks along 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 holds $9$ keys, some permutation of the digits from $1$ to $9$ . On each second, the ant can do one of three things:

Stay on its current key. The digit for that key is entered.
Move one key to the left. This is possible only if the ant is not on the leftmost key.
Move one key to the right. This is possible only if the ant is not on the rightmost key.

Find the minimum number of seconds the ant needs to type the given numeric string, over all permutations of the numeric keys.

Input

The input is a single line containing a string $s$ made only of digit characters from $1$ to $9$ ( $1 \le |s| \le 10^5$ ). This is the numeric string the ant has to type.

Output

Print one integer: the minimum number of seconds the ant needs to type the given numeric string, over all permutations of the numeric keys.

Examples1

Example 1
Input
```
78432579
```
Expected output
```
20
```