The Forbidden Permutation
Contest: Codeforces Round 848 (Div. 2)
Difficulty rating: 1300
Tags: greedy, math

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}) < \mathrm{pos}(a_{i + 1}) \le \mathrm{pos}(a_{i}) + d$$$ for all $$$1 \le i < 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) < \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).

Input format:
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$$$.

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

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
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$$$.

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$$$.

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$$$.

Example input:
5
4 2 2
1 2 3 4
1 3
5 2 4
5 4 3 2 1
5 2
5 3 3
3 4 1 5 2
3 1 2
2 2 1
1 2
2 1
6 2 4
1 2 3 4 5 6
2 5

Example output:
1
3
2
0
2

Editorial:
If the array $$$a$$$ is good, the answer is obviously $$$0$$$. Now, how can we optimally transform a not good array $$$a$$$ to a good array? Let, we are on the index $$$i$$$ $$$(i<m)$$$ and $$$x = a_i$$$, $$$y = a_{i+1}$$$. If we observe carefully, we will find that there are basically two cases that will make the array $$$a$$$ good:
1. Move $$$x$$$ and $$$y$$$ in the permutation $$$p$$$ in such a way that $$$pos(y)$$$ becomes greater than $$$pos(x) + d$$$. To do that, in the permutation $$$p$$$, we can swap $$$x$$$ to the left and $$$y$$$ to the right. The total number of swaps needed is $$$= d - (pos(y) - pos(x)) + 1$$$. We need to check if there is enough space to the left of $$$pos(x)$$$ and to the right of $$$pos(y)$$$ to perform the needed number of swaps.
2. Move $$$x$$$ and $$$y$$$ in the permutation $$$p$$$ in such a way that $$$pos(y)$$$ becomes smaller than $$$pos(x)$$$. To do that, In the permutation $$$p$$$, we can simply swap $$$y$$$ to the left until the condition is satisfied. The number of swaps needed is $$$pos(y) - pos(x)$$$.
For each $$$i < m$$$, calculate the minimum number of swaps needed among these two cases. The minimum number of swaps among all $$$i < m$$$ will be the desired answer.
Time complexity: In each test case, $$$\mathcal{O}(n)$$$