给定一个长度为 $$$n$$$ 的排列 $$$p$$$、一个由 $$$m$$$ 不同整数 $$$a_1、a_2、\ldots、a_m$$$ ($$$1 \le a_i \le n$$$) 组成的数组,以及一个整数 $$$d$$$。
设 $$$\mathrm{pos}(x)$$$ 为排列 $$$p$$$ 中 $$$x$$$ 的索引。数组 $$$a$$$ 不好,如果
- $$$\mathrm{pos}(a_{i}) < \mathrm{pos}(a_{i + 1}) \le \mathrm{pos}(a_{i}) + d$$$ 对于所有 $$$1 \le i < m$$$。
例如,对于排列 $$$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) < \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$$$)。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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$$$, $$$p_i \ne p_j$$$ for $$$i \ne j$$$)。
第三行包含 $$$m$$$ 不同的整数 $$$a_1, a_2, \ldots, a_m$$$ ($$$1\leq a_i \leq n$$$, $$$a_i \ne a_j$$$ for $$$i \ne j$$$)。
所有测试用例的 $$$n$$$ 总和不超过 $$$5 \cdot 10^5$$$。
输出
对于每个测试用例,打印使数组 $$$a$$$ 变得良好所需的最小移动次数。
示例
输入 #1
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
输出 #1
1 3 2 0 2
注意
在第一种情况下,$$$pos(a_1)=1$$$,$$$pos(a_2)=3$$$。为了使数组良好,一种方法是交换 $$$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$$$。
在第三种情况下,$$$pos(a_1)=1$$$,$$$pos(a_2)=3$$$,$$$pos(a_3)=5$$$。 $$$2$$$ 移动可以是:
1. 交换 $$$p_4$$$ 和 $$$p_5$$$。
2. 交换 $$$p_3$$$ 和 $$$p_4$$$。
第四种情况,$$$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$$$。