CF1778B.The Forbidden Permutation

You are given a permutation $p$ of length $n$, an array of $m$ distinct integers $a_1, a_2, \ldots, a_m$ ($1 \le a_i \le n$), and an integer $d$.

Let $\mathrm{pos}(x)$ be the index of $x$ in the permutation $p$. The array $a$ is not good if

• $\mathrm{pos}(a_{i}) \lt \mathrm{pos}(a_{i + 1}) \le \mathrm{pos}(a_{i}) + d$ for all $1 \le i \lt m$.

For example, with the permutation $p = [4, 2, 1, 3, 6, 5]$ and $d = 2$:

• $a = [2, 3, 6]$ is a not good array.
• $a = [2, 6, 5]$ is good because $\mathrm{pos}(a_1) = 2$, $\mathrm{pos}(a_2) = 5$, so the condition $\mathrm{pos}(a_2) \le \mathrm{pos}(a_1) + d$ is not satisfied.
• $a = [1, 6, 3]$ is good because $\mathrm{pos}(a_2) = 5$, $\mathrm{pos}(a_3) = 4$, so the condition $\mathrm{pos}(a_2) \lt \mathrm{pos}(a_3)$ is not satisfied.

In one move, you can swap two adjacent elements of the permutation $p$. What is the minimum number of moves needed such that the array $a$ becomes good? It can be shown that there always exists a sequence of moves so that the array $a$ becomes good.

A permutation is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array) and $[1,3,4]$ is also not a permutation ($n=3$, but there is $4$ in the array).

给你一个长度为 $n$ 的排列 $p$，一个由 $m$ 个互不相同的整数构成的数组 $a_1, a_2, \ldots, a_m$（其中 $1 \le a_i \le n$），以及一个整数 $d$。

令 $\mathrm{pos}(x)$ 表示元素 $x$ 在排列 $p$ 中的下标（位置）。若对所有 $1 \le i < m$ 均满足

$$\mathrm{pos}(a_{i}) \lt \mathrm{pos}(a_{i + 1}) \le \mathrm{pos}(a_{i}) + d,$$

则称数组 $a$ 不是好数组（即“not good”）。

例如，对于排列 $p = [4, 2, 1, 3, 6, 5]$ 和 $d = 2$：

• $a = [2, 3, 6]$ 是一个不是好数组；
• $a = [2, 6, 5]$ 是好数组，因为 $\mathrm{pos}(a_1) = 2$，$\mathrm{pos}(a_2) = 5$，不满足 $\mathrm{pos}(a_2) \le \mathrm{pos}(a_1) + d$；
• $a = [1, 6, 3]$ 是好数组，因为 $\mathrm{pos}(a_2) = 5$，$\mathrm{pos}(a_3) = 4$，不满足 $\mathrm{pos}(a_2) \lt \mathrm{pos}(a_3)$。

每次操作允许你交换排列 $p$ 中两个相邻的元素。问：使数组 $a$ 成为好数组所需的最少操作次数是多少？可以证明，总存在一系列操作使得 $a$ 变为好数组。

排列是指由 $1$ 到 $n$ 的 $n$ 个互不相同整数按任意顺序组成的数组。例如，$[2,3,1,5,4]$ 是一个排列；而 $[1,2,2]$ 不是排列（数字 $2$ 出现了两次），$[1,3,4]$ 也不是排列（此时 $n=3$，但数组中出现了 $4$）。

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows.

The first line of each test case contains three integers $n$, $m$ and $d$ ($2\leq n \leq 10^5$, $2\leq m\leq n$, $1 \le d \le n$), the length of the permutation $p$, the length of the array $a$ and the value of $d$.

The second line contains $n$ integers $p_1, p_2, \ldots, p_n$ ($1\leq p_i \leq n$, $p_i \ne p_j$ for $i \ne j$).

The third line contains $m$ distinct integers $a_1, a_2, \ldots, a_m$ ($1\leq a_i \leq n$, $a_i \ne a_j$ for $i \ne j$).

The sum of $n$ over all test cases doesn't exceed $5 \cdot 10^5$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$（$1 \le t \le 10^4$）。随后是各测试用例的描述。

每个测试用例的第一行包含三个整数 $n$、$m$ 和 $d$（$2\leq n \leq 10^5$，$2\leq m\leq n$，$1 \le d \le n$），分别表示排列 $p$ 的长度、数组 $a$ 的长度以及 $d$ 的值。

第二行包含 $n$ 个整数 $p_1, p_2, \ldots, p_n$（$1\leq p_i \leq n$，当 $i \ne j$ 时 $p_i \ne p_j$）。

第三行包含 $m$ 个互不相同的整数 $a_1, a_2, \ldots, a_m$（$1\leq a_i \leq n$，当 $i \ne j$ 时 $a_i \ne a_j$）。

所有测试用例中 $n$ 的总和不超过 $5 \cdot 10^5$。

For each test case, print the minimum number of moves needed such that the array $a$ becomes good.

对于每个测试用例，输出使数组 $a$ 变为“好”数组所需的最少移动次数。

In the first case, $pos(a_1)=1$, $pos(a_2)=3$. To make the array good, one way is to swap $p_3$ and $p_4$. After that, the array $a$ will be good because the condition $\mathrm{pos}(a_2) \le \mathrm{pos}(a_1) + d$ won't be satisfied.

In the second case, $pos(a_1)=1$, $pos(a_2)=4$. The $3$ moves could be:

1. Swap $p_3$ and $p_4$.
2. Swap $p_2$ and $p_3$.
3. Swap $p_1$ and $p_2$.

After these moves, the permutation $p$ will be $[2,5,4,3,1]$. The array $a$ will be good because the condition $\mathrm{pos}(a_1) \lt \mathrm{pos}(a_2)$ won't be satisfied. It can be shown that you can't make the array $a$ good with fewer moves.

In the third case, $pos(a_1)=1$, $pos(a_2)=3$, $pos(a_3)=5$. The $2$ moves can be:

1. Swap $p_4$ and $p_5$.
2. Swap $p_3$ and $p_4$.

After these moves, the permutation $p$ will be $[3,4,2,1,5]$. The array $a$ will be good because the condition $\mathrm{pos}(a_2) \lt \mathrm{pos}(a_3)$ won't be satisfied. It can be shown that you can't make the array $a$ good with fewer moves.

In the fourth case, $pos(a_1)=2$, $pos(a_2)=1$. The array $a$ is already good.

In the fifth case, $pos(a_1)=2$, $pos(a_2)=5$. The $2$ moves are:

1. Swap $p_1$ and $p_2$.
2. Swap $p_5$ and $p_6$.

第一种情况：$pos(a_1)=1$，$pos(a_2)=3$。为使数组 $a$ 变为“好”的，一种方法是交换 $p_3$ 与 $p_4$。交换后，数组 $a$ 将变为“好”的，因为条件 $\mathrm{pos}(a_2) \le \mathrm{pos}(a_1) + d$ 将不再满足。

第二种情况：$pos(a_1)=1$，$pos(a_2)=4$。这 3 次操作可以是：

1. 交换 $p_3$ 与 $p_4$；
2. 交换 $p_2$ 与 $p_3$；
3. 交换 $p_1$ 与 $p_2$。

经过这些操作后，排列 $p$ 将变为 $[2,5,4,3,1]$。此时数组 $a$ 将变为“好”的，因为条件 $\mathrm{pos}(a_1) \lt \mathrm{pos}(a_2)$ 将不再满足。可以证明：无法用少于 3 次操作使数组 $a$ 变为“好”的。

第三种情况：$pos(a_1)=1$，$pos(a_2)=3$，$pos(a_3)=5$。这 2 次操作可以是：

1. 交换 $p_4$ 与 $p_5$；
2. 交换 $p_3$ 与 $p_4$。

经过这些操作后，排列 $p$ 将变为 $[3,4,2,1,5]$。此时数组 $a$ 将变为“好”的，因为条件 $\mathrm{pos}(a_2) \lt \mathrm{pos}(a_3)$ 将不再满足。可以证明：无法用少于 2 次操作使数组 $a$ 变为“好”的。

第四种情况：$pos(a_1)=2$，$pos(a_2)=1$。数组 $a$ 已经是“好”的。

第五种情况：$pos(a_1)=2$，$pos(a_2)=5$。这 2 次操作是：

1. 交换 $p_1$ 与 $p_2$；
2. 交换 $p_5$ 与 $p_6$。