B. Запрещённая перестановка
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана перестановка $$$p$$$ длины $$$n$$$, массив из $$$m$$$ различных целых чисел $$$a_1, a_2, \ldots, a_m$$$ ($$$1 \le a_i \le n$$$) и целое число $$$d$$$.

Пусть $$$\mathrm{pos}(x)$$$ — индекс элемента $$$x$$$ в перестановке $$$p$$$. Массив $$$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$$$ становится хорошим.

Перестановка — это массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$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$$$ для $$$i \ne j$$$).

Третья строка содержит $$$m$$$ различных целых чисел $$$a_1, a_2, \ldots, a_m$$$ ($$$1\leq a_i \leq n$$$, $$$a_i \ne a_j$$$ для $$$i \ne j$$$).

Сумма $$$n$$$ по всем наборам входных данных не превосходит $$$5 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите минимальное количество ходов, необходимое для того, чтобы массив $$$a$$$ стал хорошим.

Пример
Входные данные
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
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$$$.
После этих перемещений перестановка $$$p$$$ будет иметь вид $$$[2,5,4,3,1]$$$. Массив $$$a$$$ будет хорошим, потому что условие $$$\mathrm{pos}(a_1) < \mathrm{pos}(a_2)$$$ не будет выполнено. Можно показать, что массив $$$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) < \mathrm{pos}(a_3)$$$ не будет выполнено. Можно показать, что массив $$$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$$$.