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}) < \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).

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

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

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