P16883 [GKS 2022 #D] Touchbar Typing

Glide Typing task in Crowdsource app uses a new Google keyboard to type a word by sliding a finger across keys without lifting the finger, as shown in the animation below. :::align{center}  ::: To make the Glide Typing task more challenging, instead of a normal keyboard, we have a special linear keyboard $K$ that has all the keys in one row. Imagine that you want to type a word $S$ that is $N$ characters long. The linear keyboard $K$ has $M$ keys. It is guaranteed that the keys cover all characters in $S$. However, some of the keys may be duplicates. In other words, for each character in $S$, there is one or more keys in $K$ mapped to the character. Note that, all characters and keys are represented as integers. You may start with your finger on any key. It takes $1$ second to move your finger from a key to an adjacent key. Due to Glide Typing, there is no pressing of a key. If the finger is currently at the key $i$ which has character $K_i$, and we want to type the character $K_j$ at index $j$, we will glide the finger from the key $i$ to the key $j$, which takes $|j - i|$ seconds. If your finger is at key $x$, you can type character $K_x$ any number of times instantly. You need to type string $S$ character by character. Formally, you need to type $S_i$ before $S_{i+1}$ for each $1 \le i \le N - 1$. For example, suppose the word $S$ has characters: $1, 2, 2, 3, 4$. You can start by keeping your finger on key with character $1$ on the keyboard which is at index $i$. Then you glide your finger to key which has character $2$ which is at index $j$. It would take $|j - i|$ seconds. In order to type character $2$ two times in string $S$, you can do that in no additional time as $|j - j| = 0$ seconds. Then you can continue to glide your finger to type the other characters in the word $S$ sequentially. Can you calculate the minimal time needed to type the word?

The first line of the input gives the number of test cases, $T$. $T$ test cases follow. The first line of each test case contains one integer $N$: the length of the word $S$. The second line of each test case contains $N$ integers: each $S_i$ is the character at the $i$-th index. The third line of each test case contains one integer $M$: the length of the keyboard $K$. The fourth line of each test case contains $M$ integers: each $K_i$ is the character at the $i$-th key.

For each test case, output one line containing the minimal time needed to type the word. Case #$x$: $y$, where $x$ is the test case number starting from $1$ and $y$ is the minimal time needed to type $S$ on the keyboard $K$.

In Sample Case #$1$, we can take the following steps to type string $S$ in minimum time. - Start by keeping your finger on key $K_1$ which has character $1$. We have now typed the first character of the string $S$. - In order to type the second character $2$ of the string $S$, glide your finger to key $K_2$. It takes $|2 - 1| = 1$ additional second to glide the finger from index $1$ to index $2$. - In order to type the third character $3$ of the string $S$, glide your finger to key $K_3$. It takes $|3 - 2| = 1$ additional second to glide the finger from index $2$ to index $3$. - In order to type the fourth character $2$ of the string $S$, glide your finger to key $K_2$. It takes $|2 - 3| = 1$ additional second to glide the finger from index $3$ to index $2$. - In order to type the fifth character $1$ of the string $S$, glide your finger to key $K_1$. It takes $|1 - 2| = 1$ additional second to glide the finger from index $2$ to index $1$. - We have typed all characters of the string $S$ in a total of $4$ seconds. In Sample Case #$2$, we can take the following steps to type string $S$ in minimum time. - Start by keeping your finger on key $K_2$ which has character $1$. We have now typed the first character of the string $S$. - As our finger is on key $K_2$, we can type the character $1$ any number of times, without any additional time. Hence, we can type the second and third characters of the string $S$. - We have typed all characters of the string $S$ in a total of $0$ seconds. ### Limits $1 \le T \le 100$. All characters in $S$ appears at least once in $K$. $1 \le K_i \le 2500$. $1 \le S_i \le 2500$. **Test Set $1$** $1 \le N \le 100$. $1 \le M \le 100$. It is guaranteed that there are no duplicated keys in keyboard $K$. **Test Set $2$** $1 \le N \le 100$. $1 \le M \le 100$. **Test Set $3$** $1 \le N \le 2500$. $1 \le M \le 2500$.