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

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

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


-----Examples-----

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
Output
1
3
2
0
2


-----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:

Swap $p_3$ and $p_4$.

Swap $p_2$ and $p_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:

Swap $p_4$ and $p_5$.

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:

Swap $p_1$ and $p_2$.

Swap $p_5$ and $p_6$.

Source: codeforces | Difficulty: EASY
Tags: Mathematics

Greedy algorithms


Solutions:
tc = int(input())
for _ in range(tc):
	(n, m, d) = map(int, input().split())
	pos = list(map(int, input().split()))
	cst = list(map(int, input().split()))
	dct = {}
	for i in range(n):
		dct[pos[i]] = i
	mn = 200000000000
	mx = 200000000000
	for i in range(1, m):
		length = dct[cst[i]] - dct[cst[i - 1]]
		if mn > length:
			mn = length
		if mx > d + 1 - length:
			mx = d + 1 - length
	if mn < 0 or mx < 0:
		print(0)
	elif d + 1 >= n:
		print(mn)
	else:
		print(min(mn, mx))


t = int(input())
for _ in range(0, t):
	inputs = [int(num) for num in input().split()]
	n = inputs[0]
	m = inputs[1]
	d = inputs[2]
	list1 = [int(num) for num in input().split()]
	list2 = [int(num) for num in input().split()]
	pos = [0 for i in range(0, n + 1)]
	for i in range(0, n):
		pos[list1[i]] = i
	list3 = []
	flag = 0
	moves = 0
	min1 = 1000000
	max1 = 0
	maxd = n - 1
	for i in range(0, m - 1):
		diff = pos[list2[i + 1]] - pos[list2[i]]
		if diff < min1:
			min1 = diff
		if diff > max1:
			flag = 1
			max1 = diff
	if min1 < 0 or max1 > d:
		print(0)
	elif flag == 1 and maxd >= d + 1:
		moves1 = min1
		moves2 = d + 1 - max1
		print(min(moves1, moves2))
	else:
		print(min1)


def ii(num=False):
	i = input().split()
	if num:
		return int(i[0])
	try:
		return list(map(int, i))
	except Exception:
		return i

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)
for _ in range(ii(1)):
	(n, m, d) = ii()
	p = ii()
	a = ii()
	dic = {v: i for (i, v) in enumerate(p)}
	pos = [dic[i] for i in a]
	dist = n
	for i in range(len(pos)):
		if i == 0:
			continue
		diff = pos[i] - pos[i - 1]
		if diff > d or diff < 1:
			dist = 0
			break
		dist = min(dist, diff, d - diff + 1 if d < n - 1 else n)
	print(dist)


from math import ceil

def f(a, m):
	for i in range(m - 1):
		if a[i] > a[i + 1]:
			return False
	return True
t = int(input())
for _ in range(t):
	(n, m, d) = map(int, input().split())
	p = list(map(int, input().split()))
	a = list(map(int, input().split()))
	b = set(a)
	c = list()
	f = 0
	f0 = 0
	i1 = 0
	mn = n
	mx = -1
	mxi = 0
	mxi1 = 0
	for i in range(n):
		if p[i] in b:
			c.append(p[i])
			if f:
				if i - i1 > d:
					f0 = 1
					break
				else:
					if i - i1 < mn:
						mn = i - i1
					if i - i1 > mx:
						mx = i - i1
						mxi = i
						mxi1 = i1
			f = 1
			i1 = i
	if c != a or f0:
		print(0)
	elif d >= n - 1:
		print(mn)
	else:
		print(min(mn, d - mx + 1))


def main():
	from collections import defaultdict
	t = int(input())
	for _ in range(t):
		(n, m, d) = map(int, input().split())
		p = list(map(int, input().split()))
		a = list(map(int, input().split()))
		dic = defaultdict(int)
		for i in range(n):
			dic[p[i]] = i
		ans = 1000000000
		for i in range(1, m):
			a1 = dic[a[i - 1]]
			a2 = dic[a[i]]
			if a2 < a1 or a1 + d < a2:
				ans = 0
				break
			else:
				k = 1000000000
				if d + 1 < n:
					k = d + 1 - (a2 - a1)
				k = min(k, a2 - a1)
			ans = min(ans, k)
		print(ans)
main()


for _ in range(int(input())):
	[n, m, d] = input().split()
	n = int(n)
	m = int(m)
	d = int(d)
	p = input().split()
	a = input().split()
	p = [int(o) for o in p]
	a = [int(o) for o in a]
	ind = {}
	l = []
	for u in range(n):
		ind[p[u]] = u
	for t in range(m - 1):
		x = ind[a[t + 1]] - ind[a[t]]
		l.append(x)
	if len(l) != 1 or n > d + 1:
		for y in range(len(l)):
			if l[y] > d // 2:
				l[y] = d + 1 - l[y]
	l.sort()
	ans = l[0]
	if ans > 0:
		print(ans)
	else:
		print(0)


import sys
import threading
from math import *
from bisect import *
from collections import *
from heapq import *
from functools import *

def gl():
	return list(map(int, input().split()))

def gi():
	return int(input())

def gc():
	return input()
mod = int(pow(10, 9)) + 7

def solution():
	(n, m, d) = gl()
	arr = gl()
	a = gl()
	loc = {}
	for i in range(n):
		loc[arr[i]] = i
	ans = n - 1
	for i in range(m - 1):
		if loc[a[i]] < loc[a[i + 1]]:
			if d < n - 1:
				ans = min(ans, d - (loc[a[i + 1]] - loc[a[i]]) + 1, loc[a[i + 1]] - loc[a[i]])
			else:
				ans = min(ans, loc[a[i + 1]] - loc[a[i]])
		else:
			return print(0)
	return print(max(ans, 0))

def main():
	t = gi()
	for _ in range(t):
		solution()
threading.stack_size(1 << 27)
sys.setrecursionlimit(1 << 30)
main_thread = threading.Thread(target=main)
main_thread.start()
main_thread.join()


t = int(input())
res = []
for _ in range(t):
	(n, m, d) = map(int, input().split())
	p = list(map(int, input().split()))
	a = list(map(int, input().split()))
	pos = [0 for _ in range(n + 1)]
	for i in range(n):
		pos[p[i]] = i
	op = []
	for i in range(1, m):
		if d + 1 < n:
			max_d = pos[a[i - 1]] + d - pos[a[i]] + 1
		else:
			max_d = n
		min_d = pos[a[i]] - pos[a[i - 1]]
		op.append(min(min_d, max_d))
	ans = min(op)
	if ans < 0:
		ans = 0
	res.append(ans)
for i in res:
	print(i)


t = int(input())
result = []
for i in range(t):
	(n, m, d) = list(map(int, input().split(' ')))
	pi = list(map(int, input().split(' ')))
	ai = list(map(int, input().split(' ')))
	s = []
	dict = {}
	for j in range(n):
		dict[pi[j]] = j
	for j in range(len(ai) - 1):
		(i0, i1) = (dict[ai[j]], dict[ai[j + 1]])
		if (i0 > i1) | (i0 + d < i1):
			s.append(0)
		elif d + 1 < n:
			c = d + 1 - (i1 - i0)
			s.append(min(i1 - i0, c))
		else:
			s.append(i1 - i0)
	result.append(min(s))
for i in result:
	print(i)


import sys
from os import path
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
for _ in range(int(input())):
	(n, m, d) = map(int, input().split())
	p = list(map(int, input().split()))
	a = list(map(int, input().split()))
	pos = {}
	mina = []
	flag = False
	flag2 = True
	for i in range(n):
		pos[p[i]] = i
	for i in range(m - 1):
		x = pos[a[i]]
		y = pos[a[i + 1]]
		if x < y <= x + d:
			if n - 1 >= d + 1:
				mina.append(min(y - x, d + 1 - y + x))
			else:
				mina.append(y - x)
			flag = True
		else:
			flag2 = False
			break
	if flag and flag2:
		print(min(mina))
	else:
		print(0)


def getint():
	return int(input())

def getfloat():
	return float(input())

def getints():
	return list(map(int, input().split()))

def getfloats():
	return list(map(float, input().split()))
from collections import Counter

def answer():
	(n, m, d) = getints()
	ps = getints()
	a = getints()
	dd = {}
	aa = []
	for (i, p) in enumerate(ps):
		dd[p] = i
	for _a in a:
		aa.append(dd[_a])
	ans = float('inf')
	for i in range(len(aa) - 1):
		if aa[i + 1] - aa[i] < 0 or aa[i + 1] - aa[i] > d:
			return 0
		ans = min(ans, aa[i + 1] - aa[i])
		if d < n - 1:
			ans = min(ans, d + 1 - aa[i + 1] + aa[i])
	return ans
T = getint()
for _t in range(T):
	print(answer())


def solution(n, m, d, p: list, a: list):
	p_dict = {p[i]: i for i in range(n)}
	min_r = n + 1
	flag = True
	for i in range(m - 1):
		(prev_i, next_i) = (p_dict[a[i]], p_dict[a[i + 1]])
		dd = next_i - prev_i
		if dd <= 0 or dd > d:
			flag = False
			break
		if dd > 0:
			min_r = min(min_r, dd)
		if dd <= d:
			if n - 1 - next_i + prev_i > d - dd:
				min_r = min(min_r, d - dd + 1)
	return min_r if flag else 0
t = int(input())
for _ in range(t):
	(n, m, d) = map(int, input().split())
	p = list(map(int, input().split()))
	a = list(map(int, input().split()))
	print(solution(n, m, d, p, a))


import sys
t = int(input())
for _ in range(t):
	(n, m, d) = map(int, sys.stdin.readline().split())
	v = list(map(int, input().strip().split()))
	w = list(map(int, input().strip().split()))
	mp = [0] * (n + 1)
	for i in range(0, n):
		mp[v[i]] = i
	ans = sys.maxsize
	for i in range(0, m - 1):
		nx = mp[w[i + 1]]
		ts = mp[w[i]]
		if ts > nx or nx - ts > d:
			ans = 0
		else:
			ans = min(ans, nx - ts)
			if d < n - 1:
				ans = min(ans, d - (nx - ts) + 1)
	print(ans)


for _ in range(int(input())):
	(n, m, d) = (int(x) for x in input().split(' '))
	p = [int(x) for x in input().split(' ')]
	a = [int(x) for x in input().split(' ')]
	pos = [0] * (n + 1)
	for index in range(n):
		pos[p[index]] = index
	ans = -1
	min_distance = n
	min_distance_2 = n
	for index in range(0, m - 1):
		x = pos[a[index]]
		y = pos[a[index + 1]]
		if y < x or y > x + d:
			ans = 0
			break
		else:
			min_distance = min(min_distance, y - x)
			if d - y + x < min_distance_2 and d < n - 1:
				min_distance_2 = d - y + x
	if ans == 0:
		print(0)
	else:
		tmp = min(min_distance, min_distance_2 + 1)
		print(tmp)


for i in range(int(input())):
	(n, m, d) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	p = [0 for i in range(n + 1)]
	for j in range(n):
		p[l[j]] = j
	a = list(map(int, input().split()))
	o = 100001
	for j in range(m - 1):
		k = p[a[j + 1]] - p[a[j]]
		if k < 0 or k > d:
			o = 0
			break
		else:
			o = min(o, k)
			if n - k - 1 >= d - k + 1:
				o = min(o, d - k + 1)
	print(o)


for _ in range(int(input())):
	(n, m, d) = map(int, input().split())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	l3 = [0] * n
	for i in range(n):
		l3[l1[i] - 1] = i + 1
	f = []
	for i in range(m - 1):
		x = l3[l2[i + 1] - 1] - l3[l2[i] - 1]
		if x > 0:
			if n - d >= 2:
				if d - x >= 0:
					f.append(min(d - x + 1, x))
				else:
					f.append(min(0, x))
			else:
				f.append(x)
		else:
			f.append(0)
	print(min(f))


t = int(input())
res = []
for _ in range(t):
	(n, m, d) = map(int, input().split())
	pos = [0 for _ in range(n + 1)]
	perm = list(map(int, input().split()))
	a = list(map(int, input().split()))
	mn = 1000000
	for i in range(n):
		pos[perm[i]] = i
	op = []
	for i in range(1, m):
		if d + 1 < n:
			mx = pos[a[i - 1]] + d - pos[a[i]] + 1
		else:
			mx = n
		min_d = pos[a[i]] - pos[a[i - 1]]
		mn = min(mn, min(min_d, mx))
	if mn < 0:
		mn = 0
	res.append(mn)
for i in res:
	print(i)


total = int(input())

def fun():
	(size, m, distance) = [int(s) for s in input().split(' ')]
	l = [int(s) for s in input().split(' ')]
	choices = [int(s) for s in input().split(' ')]
	d = dict()
	for (i, val) in enumerate(l):
		d[val] = i
	res = 10 ** 6
	for i in range(m - 1):
		(s1, s2) = (d[choices[i]], d[choices[i + 1]])
		if s1 > s2 or s2 > s1 + distance:
			res = 0
			break
		res = min(res, abs(s2 - s1))
		if size > distance + 1:
			res = min(res, abs(s1 + distance - s2 + 1))
	print(res)
for _ in range(total):
	fun()


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	d = int(input().split()[2])
	pa = list(map(int, input().split()))
	p = [0 for i in range(len(pa))]
	for i in range(len(pa)):
		p[pa[i] - 1] = i
	a = list(map(int, input().split()))
	last = -1
	result = 1000000000000000
	for i in a:
		elem = p[i - 1]
		if last != -1:
			if last > elem or elem - last > d:
				result = 0
				break
			else:
				result = min(result, elem - last)
				if d < len(p) - 1:
					result = min(result, d - elem + last + 1)
		last = elem
	print(result)


import bisect
from collections import defaultdict, Counter
import heapq
import math

def primes(n):
	prime = [True] * (n + 1)
	p = 2
	while p * p <= n:
		if prime[p]:
			i = p * p
			while i <= n:
				prime[i] = False
				i += p
		p += 1
	return [p for p in range(2, n + 1) if prime[p]]

def divisors(k, ps):
	if k == 0:
		return []
	result = []
	(i, p) = (0, ps[0])
	while i < len(ps) and p * p <= k:
		while k % p == 0:
			result.append(p)
			k = k // p
		i += 1
		p = ps[i]
	if k != 1:
		result.append(k)
	return result
t = int(input())
for _ in range(t):
	(n, m, d) = map(int, input().split())
	p = list(map(int, input().split()))
	a = list(map(int, input().split()))
	p2i = {pi: i for (i, pi) in enumerate(p)}
	result = float('inf')
	for (a, b) in zip(a, a[1:]):
		(ia, ib) = (p2i[a], p2i[b])
		if not ia < ib <= ia + d:
			result = 0
			break
		if d < n - 1:
			result = min(result, d + 1 - (ib - ia))
		result = min(result, ib - ia)
	print(result)


t = int(input())
res = []
for _ in range(t):
	(n, m, d) = [int(i) for i in input().split()]
	s = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	minimum = float('inf')
	ind_list = []
	prev_num_idx_s = float('inf')
	curr_num_idx_a = 0
	i = 0
	while i < n and curr_num_idx_a < m:
		if s[i] == a[curr_num_idx_a]:
			if i - prev_num_idx_s <= d:
				ind_list.append(i)
				prev_num_idx_s = i
				curr_num_idx_a += 1
		i += 1
	if curr_num_idx_a != m:
		res.append(str(0))
	else:
		for i in range(len(a) - 1):
			if n >= d + 2:
				minimum = min(minimum, d - (ind_list[i + 1] - ind_list[i]) + 1, ind_list[i + 1] - ind_list[i])
			else:
				minimum = min(minimum, ind_list[i + 1] - ind_list[i])
		res.append(str(minimum))
print('\n'.join(res))


from sys import stdin, stdout
input = stdin.readline
t = int(input())
for i in range(t):
	(n, m, d) = list(map(int, input().split()))
	p = list(map(int, input().split()))
	a = list(map(int, input().split()))
	dic = dict()
	minn = n
	for (i, j) in enumerate(p):
		dic[j] = i
	prev = dic[a[0]]
	for i in a[1:]:
		if dic[i] - prev > 0 and prev + d >= dic[i]:
			minn = min(minn, dic[i] - prev)
			if d < n - 1:
				minn = min(minn, prev + d + 1 - dic[i])
		else:
			minn = 0
		prev = dic[i]
	if minn < n:
		print(minn)
	else:
		print(0)


for _ in range(int(input())):
	(n, m, d) = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	ref = {}
	for i in range(n):
		ref[b[i]] = i
	a = [int(x) for x in input().split()]
	ans = float('inf')
	flag = 0
	for i in range(0, m - 1):
		x = ref[a[i]]
		y = ref[a[i + 1]]
		if x >= y:
			flag = 1
			break
		elif x + d < y:
			flag = 1
			break
		else:
			tmp = y - x
			if n - 1 >= d + 1:
				tmp = min(tmp, d + 1 - tmp)
			ans = min(ans, tmp)
	if flag == 1:
		print(0)
	else:
		print(ans)


import math

def solve(n, m, d, p, a):
	pos = [-1] * n
	for (i, x) in enumerate(p, 1):
		pos[x - 1] = i
	best = math.inf
	for i in range(m - 1):
		x = a[i]
		y = a[i + 1]
		if not pos[x - 1] < pos[y - 1] <= pos[x - 1] + d:
			best = 0
			break
		if d < n - 1:
			best = min(best, pos[x - 1] + d - pos[y - 1] + 1)
		best = min(best, pos[y - 1] - pos[x - 1])
	print(best)
t = int(input())
for test in range(t):
	(n, m, d) = list(map(int, input().split()))
	p = list(map(int, input().split()))
	a = list(map(int, input().split()))
	solve(n, m, d, p, a)


def solution():
	(n, m, d) = map(int, input().split())
	nums = list(map(int, input().split()))
	nums2 = list(map(int, input().split()))
	places = {val: i for (i, val) in enumerate(nums)}
	smallestIndex = -1
	smallDistance = float('inf')
	ans = float('inf')
	for i in range(m - 1):
		(f, l) = [places[nums2[i]], places[nums2[i + 1]]]
		if places[nums2[i]] > places[nums2[i + 1]] or places[nums2[i]] + d < places[nums2[i + 1]]:
			return 0
		(a, b) = [places[nums2[i]], places[nums2[i + 1]]]
		min1 = b - a
		shiftBToForward = a + d + 1
		min2 = shiftBToForward - b
		lengthOfAB = b - a + 1
		if min2 <= n - lengthOfAB:
			ans = min(ans, min(min1, min2))
		else:
			ans = min(ans, min1)
	return ans
for _ in range(int(input())):
	print(solution())


import sys, math, bisect, collections, itertools, heapq
from collections import defaultdict, deque, Counter
sys.setrecursionlimit(50000)

def mvalues():
	return map(int, sys.stdin.readline().split())

def lvalues():
	return list(map(int, sys.stdin.readline().split()))

def svalues():
	return sys.stdin.readline().strip()
for i in range(int(input())):
	(n, m, d) = mvalues()
	l1 = lvalues()
	l2 = lvalues()
	res = float('inf')
	dict1 = defaultdict()
	for (i, value) in enumerate(l1):
		dict1[value] = i
	for i in range(1, m):
		x = dict1.get(l2[i - 1])
		y = dict1.get(l2[i])
		z = y - x
		if z < 0 and y > x + d:
			res = 0
			break
		else:
			first = d - z
			res = min(z, res)
			if x + n - 1 - y > first:
				res = min(res, first + 1)
	print(max(res, 0))


t = int(input())
for o in range(t):
	(n, m, d) = map(int, input().split())
	p = list(map(int, input().split()))
	a = list(map(int, input().split()))
	position = [0] * (n + 1)
	for i in range(n):
		position[p[i]] = i + 1
	ans = n
	flag = True
	for i in range(m - 1):
		x = position[a[i]]
		y = position[a[i + 1]]
		if not (x < y and y <= x + d):
			flag = False
		if d < n - 1:
			minim = min(d - y + x + 1, y - x)
		else:
			minim = y - x
		ans = min(minim, ans)
	if flag:
		print(ans)
	else:
		print(0)


import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
	(n, m, d) = map(int, input().split())
	p = list(map(int, input().split()))
	g = [0 for _ in range(n + 1)]
	for i in range(n):
		g[p[i]] = i + 1
	lst = list(map(int, input().split()))
	new = []
	for i in lst:
		new.append(g[i])
	check = False
	mi = 1000000000.0
	ma = -1
	for i in range(m - 1):
		if new[i] < new[i + 1] and new[i + 1] - new[i] <= d:
			mi = min(mi, new[i + 1] - new[i])
			ma = max(ma, new[i + 1] - new[i])
			pass
		else:
			check = True
			break
	if check:
		print(0)
	elif n - 1 <= d:
		print(mi)
	else:
		print(min(mi, d - ma + 1))


t = int(input())
for ole in range(t):
	(n, m, d) = map(int, input().split())
	L = [int(x) for x in input().split()]
	A = [int(x) for x in input().split()]
	count = 0
	P = []
	D = {}
	for i in range(n):
		D[L[i]] = i + 1
	for i in range(m - 1):
		count = 0
		(x, y) = (D[A[i]], D[A[i + 1]])
		z = x + d
		if x < y and y <= z:
			if z + 1 <= n:
				count += min(y - x, z - y + 1)
			elif z - y + 1 <= n - y + x - 1:
				count += min(y - x, z - y + 1)
			else:
				count += y - x
		P.append(count)
	print(min(P))


for _ in range(int(input())):
	(n, m, d) = list(map(int, input().split()))
	p = list(map(int, input().split()))
	a = list(map(int, input().split()))
	di = {}
	for (index, num) in enumerate(p):
		di[num] = index
	res = float('inf')
	for i in range(m - 1):
		(u, v) = (di[a[i]], di[a[i + 1]])
		if u > v or v - u > d:
			res = 0
			break
		out = float('inf')
		if d < n - 1:
			out = d + 1 - (v - u)
		swap = v - u
		res = min(out, swap, res)
	print(res)


def solve1():
	n = int(input())
	a = list(map(int, input().split()))
	s = 0
	flag = False
	for i in range(1, n):
		if a[i] == a[i - 1] == -1:
			return sum(a) + 4
		elif a[i] == -1 or a[i - 1] == -1:
			flag = True
	if flag:
		return sum(a)
	return sum(a) - 4

def solve():
	(n, m, d) = map(int, input().split())
	p = list(map(int, input().split()))
	a = list(map(int, input().split()))
	pos = {p[i]: i for i in range(n)}
	ans = float('inf')
	for i in range(m - 1):
		if pos[a[i + 1]] <= pos[a[i]] or pos[a[i + 1]] - pos[a[i]] > d:
			return 0
		ans = min(ans, pos[a[i + 1]] - pos[a[i]])
		dist = pos[a[i + 1]] - pos[a[i]]
		swapNeed = d - dist + 1
		swapPossible = pos[a[i]] - 1 + (n - pos[a[i + 1]])
		if swapPossible >= swapNeed:
			ans = min(ans, swapNeed)
	return ans
for _ in range(int(input())):
	ans = solve()
	print(ans)


t = int(input())
for _ in range(t):
	locs = {}
	(n, m, d) = [int(x) for x in input().split()]
	p = [int(x) for x in input().split()]
	arr = [int(x) for x in input().split()]
	locs = {}
	for i in range(len(p)):
		locs[p[i]] = i
	minFix = len(p)
	for i in range(len(arr) - 1):
		(p1, p2) = (locs[arr[i]], locs[arr[i + 1]])
		if 0 > p2 - p1 or p2 - p1 > d:
			minFix = 0
			break
		if p2 + d - (p2 - p1) + 1 < n or p1 - (d - (p2 - p1) + 1) >= 0:
			minFix = min(minFix, d - (p2 - p1) + 1)
		elif n - p2 - 1 + p1 > d - (p2 - p1):
			minFix = min(minFix, d - (p2 - p1) + 1)
		minFix = min(minFix, p2 - p1)
	print(minFix)
	leftleftMost = 0


import math
t = int(input())
for _ in range(t):
	(m, n, d) = map(int, input().split())
	perm = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	idx = {perm[i]: i for i in range(len(perm))}
	ans = math.inf
	for i in range(1, len(arr)):
		(l, r) = (idx[arr[i - 1]], idx[arr[i]])
		if l < r:
			ans = min(r - l, ans)
		if d + l >= r:
			temp = l + len(perm) - r - 1
			if l + d - r < temp:
				ans = min(ans, l + d - r + 1)
		if r <= l or d + l < r:
			ans = 0
	print(ans)


from math import *
for _ in range(int(input())):
	(n, m, k) = map(int, input().split())
	p = list(map(int, input().split()))
	a = list(map(int, input().split()))
	d = {}
	for i in range(n):
		d[p[i]] = i
	ans = n + 10
	for i in range(m - 1):
		if d[a[i]] < d[a[i + 1]] and d[a[i]] + k >= d[a[i + 1]]:
			ans = min(ans, d[a[i + 1]] - d[a[i]])
			if k < n - 1:
				ans = min(ans, d[a[i]] - d[a[i + 1]] + k + 1)
		else:
			ans = 0
	print(ans)


for _ in range(int(input())):
	inp = lambda : map(int, input().split())
	(n, m, d) = inp()
	p = [0] + list(inp())
	a = list(inp())
	pos = [0] * (n + 1)
	for i in range(1, n + 1):
		pos[p[i]] = i
	mn = n
	used = m - 1
	for i in range(m - 1):
		if pos[a[i]] < pos[a[i + 1]] <= pos[a[i]] + d:
			to_min = [mn, pos[a[i + 1]] - pos[a[i]]]
			mn = min(to_min + ([d + 1 - (pos[a[i + 1]] - pos[a[i]])] if d < n - 1 else []))
			used -= 1
	print(0 if used else mn)


for i in range(int(input())):
	(n, m, d) = map(int, input().split())
	p = list(map(int, input().split()))
	a = list(map(int, input().split()))
	ans = n + 1
	v = {}
	for k in range(n):
		v[p[k]] = k
	for j in range(m - 1):
		if v[a[j]] < v[a[j + 1]] <= v[a[j]] + d:
			ans = min(ans, v[a[j + 1]] - v[a[j]])
			if d < n - 1:
				ans = min(ans, v[a[j]] - v[a[j + 1]] + d + 1)
		else:
			ans = 0
	print(ans)


from math import *
for j in range(int(input())):
	(har, m1, k) = map(int, input().split())
	p = list(map(int, input().split()))
	a = list(map(int, input().split()))
	d = {}
	for i in range(har):
		d[p[i]] = i
	ans = har + 10
	for i in range(m1 - 1):
		if d[a[i]] < d[a[i + 1]] and d[a[i]] + k >= d[a[i + 1]]:
			ans = min(ans, d[a[i + 1]] - d[a[i]])
			if k < har - 1:
				ans = min(ans, d[a[i]] - d[a[i + 1]] + k + 1)
		else:
			ans = 0
	print(ans)


import sys
for t in range(int(input())):
	(n, m, d) = list(map(int, input().split()))
	p = list(map(int, input().split()))
	a = list(map(int, input().split()))
	pos = {}
	for i in range(n):
		pos[p[i]] = i
	isGood = False
	for i in range(m - 1):
		if pos[a[i]] > pos[a[i + 1]] or pos[a[i + 1]] > pos[a[i]] + d:
			isGood = True
			break
	if isGood:
		print(0)
	else:
		ans = sys.maxsize
		for i in range(m - 1):
			ans = min(ans, pos[a[i + 1]] - pos[a[i]])
		if d + 1 < n:
			for i in range(m - 1):
				ans = min(ans, d + 1 - (pos[a[i + 1]] - pos[a[i]]))
		print(ans)


t = int(input())
ans = []
for ti in range(t):
	(n, m, d) = [int(x) for x in input().split()]
	p = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	p1 = [0] * (n + 1)
	for i in range(n):
		p1[p[i]] = i + 1
	a1 = [0] * m
	min_r = n
	for i in range(m):
		a1[i] = p1[a[i]]
		if i > 0:
			min_r = min(min_r, a1[i] - a1[i - 1])
			r = a1[i - 1] + d - a1[i] + 1
			if a1[i] + r - (a1[i - 1] - 1) <= n:
				min_r = min(min_r, r)
		if min_r <= 0:
			break
	ans.append(max(0, min_r))
for a in ans:
	print(a)


import os
import math
import collections
import bisect
import functools
import itertools
import heapq

def solve(a, p, m, n, d):
	dic = {x: i for (i, x) in enumerate(p)}
	ans = float('inf')
	for i in range(m - 1):
		(i1, i2) = (dic[a[i]], dic[a[i + 1]])
		if not i1 < i2 <= i1 + d:
			return 0
		v = i2 - i1
		d1 = max(0, i1)
		d2 = max(0, n - 1 - i2)
		if i2 - 1 - d >= 0:
			v = min(v, i1 + d - i2 + 1)
		if i1 + d + 1 < n:
			v = min(v, i1 + d + 1 - i2)
		if i2 - i1 + d1 + d2 > d:
			v = min(v, d + 1 - (i2 - i1))
		ans = min(ans, v)
	return ans
t = int(input())
for _ in range(t):
	(n, m, d) = map(int, input().split())
	p = list(map(int, input().split()))
	a = list(map(int, input().split()))
	print(solve(a, p, m, n, d))


t = int(input())
for _ in range(t):
	things = [int(x) for x in input().split()]
	d = things[2]
	perm = [int(x) for x in input().split()]
	arr = [int(x) for x in input().split()]
	dperm = {}
	for i in range(len(perm)):
		dperm[perm[i]] = i
	good = False
	m = len(perm)
	for i in range(len(arr) - 1):
		if not dperm[arr[i]] < dperm[arr[i + 1]] or not dperm[arr[i]] + d >= dperm[arr[i + 1]]:
			good = True
		a = dperm[arr[i + 1]] - dperm[arr[i]]
		b = d - dperm[arr[i + 1]] + dperm[arr[i]] + 1
		if len(perm) > d + 1:
			m = min(m, a, b)
		else:
			m = min(m, a)
	if good:
		print(0)
	else:
		print(m)


t = int(input())
for _ in range(t):
	(n, m, d) = map(int, input().split())
	p = [(index, i - 1) for (index, i) in enumerate(list(map(int, input().split())))]
	a = [i - 1 for i in list(map(int, input().split()))]
	p.sort(key=lambda i: i[1])
	ans = 100005
	for i in range(m - 1):
		dist = p[a[i + 1]][0] - p[a[i]][0]
		if dist < 0 or dist > d:
			ans = 0
			break
		if d >= n - 1:
			ans = min(ans, dist)
		else:
			ans = min(ans, dist, d - dist + 1)
	print(ans)


xyz = int(input())
for _ in range(xyz):
	l = [int(x) for x in input().split()]
	n = l[0]
	m = l[1]
	d = l[2]
	p = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	l = [-1 for i in range(n + 1)]
	t = 0
	mmm = n
	for i in range(n):
		l[p[i]] = i + 1
	for i in range(m - 1):
		if l[a[i + 1]] - l[a[i]] < 0:
			print(0)
			t = 1
			break
		elif l[a[i + 1]] - l[a[i]] > d:
			print(0)
			t = 1
			break
		else:
			x = l[a[i + 1]] - l[a[i]]
			y = l[a[i]] - 1 + n - l[a[i + 1]]
			if x + y > d:
				mmm = min(mmm, min(x, d - x + 1))
			else:
				mmm = min(mmm, x)
	if t == 1:
		continue
	else:
		print(mmm)


t = int(input())
while t:
	(n, m, d) = map(int, input().split())
	p = list(map(int, input().split()))
	l = list(map(int, input().split()))
	info = {}
	ans = 1000000000
	for i in range(n):
		info[p[i]] = i
	flag = 0
	for j in range(m - 1):
		if info[l[j]] > info[l[j + 1]] or info[l[j + 1]] > info[l[j]] + d:
			flag = 1
			break
		else:
			req = d + 1 - (info[l[j + 1]] - info[l[j]])
			if info[l[j]] - 0 + n - 1 - info[l[j + 1]] >= req:
				ans = min(ans, req)
			ans = min(ans, info[l[j + 1]] - info[l[j]])
	if flag == 1:
		print(0)
	else:
		print(ans)
	t -= 1


for _ in range(int(input())):
	(n, m, d) = map(int, input().split())
	p = list(map(int, input().split()))
	a = list(map(int, input().split()))
	pos = [0] * (n + 1)
	min_move = n
	for i in range(n):
		x = p[i]
		pos[x] = i + 1
	for i in range(m - 1):
		if pos[a[i]] > pos[a[i + 1]]:
			min_move = 0
			break
		elif pos[a[i]] + d < pos[a[i + 1]]:
			min_move = 0
			break
		else:
			min_move = min(min_move, pos[a[i + 1]] - pos[a[i]])
			moves = d - (pos[a[i + 1]] - pos[a[i]]) + 1
			if moves <= pos[a[i]] - 1 + n - pos[a[i + 1]]:
				min_move = min(min_move, moves)
	print(min_move)


import math
for _ in range(int(input())):
	(n, m, d) = map(int, input().split())
	p = list(map(int, input().split()))
	a = list(map(int, input().split()))
	mi = 1000000000.0
	ans = 0
	ind = [0] * n
	for i in range(n):
		ind[p[i] - 1] = i + 1
	for i in range(m - 1):
		if ind[a[i] - 1] < ind[a[i + 1] - 1]:
			if ind[a[i + 1] - 1] > ind[a[i] - 1] + d:
				ans = -1
				break
			elif 1 + d < n:
				mi = min(mi, ind[a[i + 1] - 1] - ind[a[i] - 1], ind[a[i] - 1] + d - ind[a[i + 1] - 1] + 1)
			else:
				mi = min(mi, ind[a[i + 1] - 1] - ind[a[i] - 1])
		else:
			ans = -1
			break
	if ans == -1:
		print(0)
	else:
		print(mi)


for _ in range(int(input())):
	(n, m, d) = map(int, input().strip().split())
	p = [0] + list(map(int, input().strip().split()))
	pos = [0 for i in range(max(p) + 1)]
	for i in range(1, n + 1):
		pos[p[i]] = i
	a = [0] + list(map(int, input().strip().split()))
	ans = int(1000000000.0)
	for i in range(1, m):
		if pos[a[i + 1]] <= pos[a[i]] or pos[a[i + 1]] - pos[a[i]] > d:
			ans = 0
			break
		ans = min(ans, pos[a[i + 1]] - pos[a[i]])
		dist = pos[a[i + 1]] - pos[a[i]]
		swap_needed = d - dist + 1
		swap_possible = pos[a[i]] - 1 + (n - pos[a[i + 1]])
		if swap_possible >= swap_needed:
			ans = min(ans, swap_needed)
	print(ans)


def nop():
	t = int(input().strip())
	for _ in range(t):
		(n, m, d) = map(int, input().strip().split())
		p = list(map(int, input().strip().split()))
		a = list(map(int, input().strip().split()))
		pos = [0] * (n + 1)
		pos[0] = float('inf')
		cnt = 0
		ans = float('inf')
		for i in range(n):
			pos[p[i]] = i + 1
		for i in range(m - 1):
			if pos[a[i]] > pos[a[i + 1]]:
				cnt += 1
				break
			elif pos[a[i + 1]] > pos[a[i]] + d:
				cnt += 1
				break
			else:
				ans = min(ans, pos[a[i + 1]] - pos[a[i]])
				x = pos[a[i]] + d - pos[a[i + 1]] + 1
				if x <= pos[a[i]] - 1:
					ans = min(ans, x)
				x1 = pos[a[i]] + d - pos[a[i + 1]] + 1
				if x1 <= n - pos[a[i + 1]]:
					ans = min(ans, x1)
				if pos[a[i]] - 1 + n - pos[a[i + 1]] >= x:
					ans = min(ans, x)
		if cnt > 0:
			print(0)
		else:
			print(ans)
nop()


import sys
input = sys.stdin.readline
T = int(input())
for i in range(T):
	(n, m, d) = map(int, input().split())
	p = list(map(int, input().split()))
	index = {}
	a = list(map(int, input().split()))
	for i in range(n):
		index[p[i]] = i + 1
	can = set()
	for i in range(m - 1):
		if index[a[i]] >= index[a[i + 1]]:
			can.add(0)
			break
		elif index[a[i + 1]] > index[a[i]] + d:
			can.add(0)
			break
		else:
			can.add(index[a[i + 1]] - index[a[i]])
			if index[a[i]] - 1 + (n - index[a[i + 1]]) > index[a[i]] + d - index[a[i + 1]]:
				can.add(index[a[i]] + d - index[a[i + 1]] + 1)
	print(min(can))


import sys
import math
MOD = int(1000000000.0 + 7)

def power(a, b):
	ans = 1
	while b:
		if b & 1:
			ans = ans * a % MOD
		a = a * a % MOD
		b >>= 1
	return ans

def power1(a, b):
	ans = 1
	while b:
		if b & 1:
			ans = ans * a
		a = a * a
		b >>= 1
	return ans
t = int(input().strip())
for _ in range(t):
	(n, m, d) = map(int, input().strip().split())
	vec = list(map(int, input().strip().split()))
	mp = {}
	for (i, val) in enumerate(vec):
		mp[val] = i + 1
	tp = [0] + list(map(int, input().strip().split()))
	ans = int(100000000000000.0)
	y = 0
	for i in range(1, m):
		if mp[tp[i]] < mp[tp[i + 1]] and mp[tp[i + 1]] <= mp[tp[i]] + d:
			ans1 = mp[tp[i + 1]] - mp[tp[i]]
			ans2 = mp[tp[i]] + d + 1 - mp[tp[i + 1]]
			num = mp[tp[i]] + d + 1 - n
			div = int(100000000000000.0)
			ag = mp[tp[i]] + d + 1
			if ag > n and mp[tp[i]] >= 1 + num:
				div = n - mp[tp[i + 1]] + num
			if ag > n:
				ans2 = int(100000000000000.0)
			ans = min(ans, min(ans1, min(ans2, div)))
		else:
			y = 1
	if y == 1:
		ans = 0
	print(ans)


t = int(input())
for _ in range(t):
	(n, m, d) = [int(i) for i in input().split()]
	p = [int(i) for i in input().split()]
	a = [int(i) for i in input().split()]
	pos = [0] * (n + 1)
	for i in range(n):
		pos[p[i]] = i + 1
	res = 10 ** 10
	for i in range(m - 1):
		if pos[a[i]] < pos[a[i + 1]] <= pos[a[i]] + d:
			res = min(res, pos[a[i + 1]] - pos[a[i]])
			mb = pos[a[i]] + d + 1 - pos[a[i + 1]]
			if min(pos[a[i]] - 1, n - pos[a[i]]) + min(pos[a[i + 1]] - 1, n - pos[a[i + 1]]) - mb >= 0:
				res = min(res, mb)
		else:
			print(0)
			break
	else:
		print(res)


inf = int(1e+18)
for _ in range(int(input())):
	(n, m, d) = map(int, input().split())
	permutation = [int(x) for x in input().split()]
	arr = [int(x) for x in input().split()]
	position = {}
	for i in range(n):
		position[permutation[i]] = i + 1
	res = inf
	no_need = False
	for i in range(m - 1):
		(left_a, right_b) = (inf, inf)
		if position[arr[i]] < position[arr[i + 1]] <= position[arr[i]] + d:
			b_a = position[arr[i + 1]] - position[arr[i]]
		else:
			no_need = True
			break
		space = position[arr[i + 1]] - position[arr[i]]
		needed = d - space + 1
		if position[arr[i]] - needed > 0:
			left_a = needed
		if position[arr[i + 1]] + needed <= n:
			right_b = needed
		left_over = position[arr[i]] - 1 + (n - position[arr[i + 1]])
		req = inf
		if left_over - needed >= 0:
			req = needed
		res = min(res, b_a, right_b, left_a, req)
	if no_need:
		print(0)
	else:
		print(res)


t = int(input())
for i in range(t):
	(n, m, d) = list(map(int, input().split(sep=' ')))
	p = list(map(int, input().split(sep=' ')))
	a = list(map(int, input().split(sep=' ')))
	mat = [[0 for j in range(2)] for k in range(n)]
	cnt1 = 0
	cnt2 = 0
	cnt = 99999999999
	for j in range(n):
		e = p[j]
		mat[e - 1] = [e, j + 1]
	for j in range(m - 1):
		e1 = a[j]
		e2 = a[j + 1]
		x = mat[e1 - 1][1]
		y = mat[e2 - 1][1]
		if x > y or y > x + d:
			cnt = 0
			break
		elif 1:
			cnt1 = y - x
			if d < n - 1:
				cnt2 += x + d + 1 - y
			else:
				cnt2 = cnt1 + 1
		cnt = min(cnt, min(cnt1, cnt2))
		cnt1 = 0
		cnt2 = 0
	print(cnt)