"If you didn't copy assignments during your engineering course, did you even do engineering?"
There are $Q$ students in Chef's class. Chef's teacher has given the students a simple assignment:
Write a function that takes as arguments an array $A$ containing only unique elements and a number $X$ guaranteed to be present in the array and returns the ($1$-based) index of the element that is equal to $X$.
The teacher was expecting a linear search algorithm, but since Chef is such an amazing programmer, he decided to write the following binary search function:
integer binary_search(array a, integer n, integer x):
integer low, high, mid
low := 1
high := n
while low ≤ high:
mid := (low + high) / 2
if a[mid] == x:
break
else if a[mid] is less than x:
low := mid+1
else:
high := mid-1
return mid

All of Chef's classmates have copied his code and submitted it to the teacher.
Chef later realised that since he forgot to sort the array, the binary search algorithm may not work. Luckily, the teacher is tired today, so she asked Chef to assist her with grading the codes. Each student's code is graded by providing an array $A$ and an integer $X$ to it and checking if the returned index is correct. However, the teacher is lazy and provides the exact same array to all codes. The only thing that varies is the value of $X$.
Chef was asked to type in the inputs. He decides that when typing in the input array for each code, he's not going to use the input array he's given, but an array created by swapping some pairs of elements of this original input array. However, he cannot change the position of the element that's equal to $X$ itself, since that would be suspicious.
For each of the $Q$ students, Chef would like to know the minimum number of swaps required to make the algorithm find the correct answer.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains two space-separated integers $N$ and $Q$ denoting the number of elements in the array and the number of students.
- The second line contains $N$ space-separated integers $A_1, A_2, \dots, A_N$.
- The following $Q$ lines describe queries. Each of these lines contains a single integer $X$.

-----Output-----
For each query, print a single line containing one integer — the minimum required number of swaps, or $-1$ if it is impossible to make the algorithm find the correct answer. (Do you really think Chef can fail?)

-----Constraints-----
- $1 \le T \le 10$
- $1 \le N, Q \le 10^5$
- $1 \le A_i \le 10^9$ for each valid $i$
- $1 \le X \le 10^9$
- all elements of $A$ are pairwise distinct
- for each query, $X$ is present in $A$
- sum of $N$ over all test cases $\le 5\cdot10^5$
- sum of $Q$ over all test cases $\le 5\cdot10^5$

-----Subtasks-----
Subtask #1 (20 points): $1 \le N \le 10$
Subtask #2 (30 points):
- $1 \le A_i \le 10^6$ for each valid $i$
- $1 \le X \le 10^6$
Subtask #3 (50 points): original constraints

-----Example Input-----
1
7 7
3 1 6 7 2 5 4
1
2
3
4
5
6
7

-----Example Output-----
0
1
1
2
1
0
0

-----Explanation-----
Example case 1:
- Query 1: The algorithm works without any swaps.
- Query 2: One solution is to swap $A_2$ and $A_4$.
- Query 3: One solution is to swap $A_2$ and $A_6$.
- Query 4: One solution is to swap $A_2$ with $A_4$ and $A_5$ with $A_6$.
- Query 5: One solution is to swap $A_2$ and $A_4$.
- Query 6: The algorithm works without any swaps.
- Query 7: The algorithm works without any swaps.

Source: codechef | Difficulty: MEDIUM_HARD
Tags: Sorting


Solutions:
t = int(input())
for m in range(t):
	(n, q) = map(int, input().split())
	arr = [int(x) for x in input().split()]
	grap = {}
	for i in range(n):
		grap[arr[i]] = i
	arr2 = sorted(arr)
	grap2 = {}
	for i in range(n):
		grap2[arr2[i]] = i
	for l in range(q):
		x = int(input())
		low = 0
		high = n - 1
		left = 0
		right = 0
		flag = 0
		swap = 0
		mini_ele = grap2[x]
		maxi_ele = n - 1 - grap2[x]
		while low <= high:
			mid = (low + high) // 2
			if arr[mid] == x:
				break
			elif grap[x] > mid:
				if arr[mid] < x:
					low = mid + 1
				else:
					if right == 0:
						swap += 1
						left += 1
					else:
						right -= 1
					low = mid + 1
				mini_ele -= 1
				if mini_ele < 0:
					flag = 1
					break
			else:
				if arr[mid] > x:
					high = mid - 1
				else:
					if left == 0:
						swap += 1
						right += 1
					else:
						left -= 1
					high = mid - 1
				maxi_ele -= 1
				if maxi_ele < 0:
					flag = 1
					break
		if flag == 1:
			print(-1)
		else:
			print(swap)


from sys import stdin, stdout
t = int(stdin.readline())
while t:
	(n, q) = list(map(int, stdin.readline().rstrip().split()))
	arr = list(map(int, stdin.readline().rstrip().split()))
	d = {}
	d1 = {}
	a = arr.copy()
	a.sort()
	for i in range(n):
		d1[a[i]] = i
		d[arr[i]] = i
	while q:
		v = int(stdin.readline().rstrip())
		index = d[v]
		smaller = d1[v]
		bigger = n - smaller - 1
		(low, high) = (0, n - 1)
		(c1, c2) = (0, 0)
		while high >= low:
			mid = (high + low) // 2
			if mid == index:
				break
			elif index > mid:
				if arr[mid] > v:
					c1 += 1
				else:
					smaller -= 1
				low = mid + 1
			else:
				if v > arr[mid]:
					c2 += 1
				else:
					bigger -= 1
				high = mid - 1
		if c2 > c1:
			if bigger >= c2 - c1:
				print(c2)
			else:
				print(-1)
		elif c1 > c2:
			if smaller >= c1 - c2:
				print(c1)
			else:
				print(-1)
		else:
			print(c1)
		q -= 1
	t -= 1


def bst2(B, n, number):
	l = 0
	h = n - 1
	while l <= h:
		m = l + h >> 1
		if B[m] == number:
			return m
		elif B[m] > number:
			h = m - 1
		else:
			l = m + 1

def BST(A, n, index, i):
	(l, h) = (0, n - 1)
	lm = ln = 0
	lm1 = ln1 = 0
	while l <= h:
		m = l + h >> 1
		if m == index:
			break
		elif m < index:
			l = m + 1
			if A[m] > A[index]:
				ln += 1
			else:
				ln1 += 1
		else:
			h = m - 1
			if A[m] < A[index]:
				lm += 1
			else:
				lm1 += 1
	if ln <= i - ln1 and lm <= n - i - 1 - lm1:
		return max(lm, ln)
	return -1
for _ in range(int(input())):
	memo = {}
	(n, q) = list(map(int, input().split()))
	A = list(map(int, input().split()))
	B = sorted(A)
	for i in range(n):
		memo[A[i]] = i
	for _ in range(q):
		x = int(input())
		i = bst2(B, n, x)
		print(BST(A, n, memo[x], i))


T = int(input())
for cases in range(T):
	(N, Q) = map(int, input().split())
	A = list(map(int, input().split()))
	Asorted = A[:]
	Asorted.sort()
	pos = {}
	Sortpos = {}
	for i in range(N):
		pos[A[i]] = i
	for i in range(N):
		Sortpos[Asorted[i]] = i
	for i in range(Q):
		X = int(input())
		low = 0
		high = N - 1
		mid = (low + high) // 2
		cg = 0
		cl = 0
		a = 0
		b = 0
		while low <= high and A[mid] != X:
			mid = (low + high) // 2
			if A[mid] > X:
				if pos[X] > mid:
					cg += 1
					low = mid + 1
				if pos[X] < mid:
					high = mid - 1
					b += 1
			elif A[mid] < X:
				if pos[X] > mid:
					low = mid + 1
					a += 1
				if pos[X] < mid:
					cl += 1
					high = mid - 1
		p = Sortpos[X]
		if cg == cl:
			print(cl)
		elif cl > cg:
			if cl + b <= N - p - 1:
				print(cl)
			else:
				print(-1)
		elif cg + a <= p:
			print(cg)
		else:
			print(-1)


for t in range(int(input())):
	(n, q) = map(int, input().split())
	arr = list(map(int, input().split()))
	brr = []
	pos = {}
	bpos = {}
	for i in range(n):
		pos[arr[i]] = i
		brr.append(arr[i])
	brr.sort()
	for j in range(n):
		bpos[brr[j]] = j
	for i in range(q):
		x = int(input())
		low = 0
		high = n - 1
		il = ir = cl = cr = 0
		while low <= high:
			mid = (low + high) // 2
			if arr[mid] == x:
				break
			elif x < arr[mid] and pos[x] < mid:
				cl += 1
				high = mid - 1
			elif x < arr[mid] and pos[x] > mid:
				ir += 1
				low = mid + 1
			elif x > arr[mid] and pos[x] > mid:
				cr += 1
				low = mid + 1
			else:
				il += 1
				high = mid - 1
		indx = bpos[x]
		elemLessThan = indx
		elemMoreThan = n - indx - 1
		if cr + ir <= elemLessThan and cl + il <= elemMoreThan:
			print(max(ir, il))
		else:
			print(-1)


for _ in range(int(input())):
	(n, q) = list(map(int, input().split()))
	l = [int(i) for i in input().split()]
	d = {}
	ind = {}
	for i in range(n):
		ind[l[i]] = i
	dup = l[:]
	dup = sorted(dup)
	for i in range(n):
		chote = i
		bade = n - i - 1
		d[dup[i]] = [chote, bade]
	for _ in range(q):
		chotewale_swap = 0
		badewale_swap = 0
		x = int(input())
		d1 = d[x].copy()
		f = 1
		low = 0
		high = n - 1
		while low <= high:
			mid = (low + high) // 2
			if ind[x] == mid:
				break
			elif ind[x] > mid and x > l[mid]:
				d1[0] -= 1
				low = mid + 1
			elif ind[x] > mid and x < l[mid]:
				if d1[0] == 0:
					f = -1
					break
				d1[0] -= 1
				chotewale_swap += 1
				low = mid + 1
			elif ind[x] < mid and x < l[mid]:
				d1[1] -= 1
				high = mid - 1
			elif ind[x] < mid and x > l[mid]:
				if d1[1] == 0:
					f = -1
					break
				d1[1] -= 1
				badewale_swap += 1
				high = mid - 1
		if f == -1:
			print(-1)
		else:
			print(max(chotewale_swap, badewale_swap))


t = int(input())
for tc in range(t):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	ac = sorted(a)
	fa = {}
	indices = {}
	for i in range(n):
		indices[a[i]] = i
	for query in range(q):
		x = int(input())
		if fa.get(x, -2) == -2:
			realI = indices[x]
			lo = 0
			hi = n - 1
			mid = lo + (hi - lo) // 2
			while lo <= hi:
				mid = lo + (hi - lo) // 2
				if ac[mid] == x:
					break
				elif ac[mid] < x:
					lo = mid + 1
				else:
					hi = mid - 1
			ic = mid
			ndts = 0
			ndtl = 0
			bigneed = 0
			smallneed = 0
			lo = 0
			hi = n - 1
			while lo <= hi:
				mid = lo + (hi - lo) // 2
				if a[mid] == x:
					break
				elif mid < realI:
					lo = mid + 1
					if a[mid] < x:
						ndts += 1
					else:
						smallneed += 1
				elif mid > realI:
					hi = mid - 1
					if a[mid] > x:
						ndtl += 1
					else:
						bigneed += 1
			bigpresent = n - ic - 1 - ndtl
			smallpresent = ic - ndts
			if bigneed <= bigpresent and smallneed <= smallpresent:
				swaps = 0
				mn = min(bigneed, smallneed)
				swaps += mn
				swaps += bigneed + smallneed - 2 * mn
				fa[x] = swaps
				print(swaps)
			else:
				fa[x] = -1
				print(-1)
		else:
			print(fa[x])


def modified_binary(a, key, l, u):
	while l <= u:
		mid = (l + u) // 2
		if a[mid][0] == key:
			break
		elif a[mid][0] > key:
			u = mid - 1
		else:
			l = mid + 1
	return [a[mid][1], mid]
for _ in range(int(input())):
	(n, q) = [int(x) for x in input().split()]
	a1 = input().split()
	a = [[int(a1[x]), x] for x in range(n)]
	e = sorted(a, key=lambda x: x[0])
	m = []
	for x in range(q):
		m.append(int(input()))
	for key in m:
		p = 0
		(index, left) = modified_binary(e, key, 0, n - 1)
		right = n - 1 - left
		ini = 0
		last = n - 1
		(l, r, h, u1, u2) = (0, 0, 0, 0, 0)
		while last >= ini:
			mid = (ini + last) // 2
			if mid == index:
				break
			elif mid > index:
				if a[mid][0] < key:
					r += 1
				else:
					u2 += 1
				last = mid - 1
			else:
				if a[mid][0] > key:
					l += 1
				else:
					u1 += 1
				ini = mid + 1
			h += 1
		if right - u2 >= r and left - u1 >= l:
			swap = h - min(l, r) - u1 - u2
			p = 1
		if p == 1:
			print(swap)
		else:
			print(-1)


import copy

def binary_search(a, b, C, n, k, x):
	low = 0
	z = n - k - 1
	high = n - 1
	c1 = 0
	c2 = 0
	flag = 0
	while low <= high:
		mid = (low + high) // 2
		if a[mid] == x:
			break
		elif a[mid] > x:
			if mid < b[x]:
				low = mid + 1
				c1 += 1
			else:
				high = mid - 1
				z -= 1
		elif a[mid] < x:
			if mid > b[x]:
				high = mid - 1
				c2 += 1
			else:
				low = mid + 1
				k -= 1
	if c1 <= k and c2 <= z:
		return max(c1, c2)
	else:
		return -1
T = int(input())
for t in range(T):
	(N, Q) = map(int, input().split())
	A = list(map(int, input().split()))
	B = {}
	D = {}
	C = sorted(A)
	for n in range(N):
		B[A[n]] = n
		D[C[n]] = n
	for q in range(Q):
		X = int(input())
		print(binary_search(A, B, C, N, D[X], X))


from operator import itemgetter
R = lambda : map(int, input().split())
t = int(input())
for _ in range(t):
	(n, q) = R()
	a = list(R())
	b = sorted(enumerate(a), key=itemgetter(1))
	d = dict(((x, (i, j)) for (j, (i, x)) in enumerate(b)))
	for _ in range(q):
		x = int(input())
		(i, j) = d[x]
		(l, h) = (0, n - 1)
		a1 = a2 = b1 = b2 = 0
		while True:
			m = (l + h) // 2
			if m == i:
				break
			if m < i:
				l = m + 1
				a1 += 1
				if a[m] > x:
					a2 += 1
			else:
				h = m - 1
				b1 += 1
				if a[m] < x:
					b2 += 1
		if a1 > j or b1 > n - 1 - j:
			print(-1)
		else:
			print(max(a2, b2))


from collections import OrderedDict
T = int(input())
for test_case in range(T):
	(N, Q) = map(int, input().split())
	a = list(map(int, input().split()))
	d = {a[i]: i + 1 for i in range(N)}
	a_sort = sorted(a)
	d_sort = OrderedDict()
	for i in range(N):
		d_sort[a_sort[i]] = i
	for query in range(Q):
		x = int(input())
		(cntl, cnth) = (0, 0)
		(l, h) = (d_sort[x], N - 1 - d_sort[x])
		low = 1
		high = N
		while low <= high:
			mid = (low + high) // 2
			if a[mid - 1] == x:
				break
			elif a[mid - 1] < x:
				if d[x] < mid:
					cnth += 1
					h -= 1
					high = mid - 1
				else:
					l -= 1
					low = mid + 1
			elif d[x] > mid:
				cntl += 1
				l -= 1
				low = mid + 1
			else:
				h -= 1
				high = mid - 1
		if l < 0 or h < 0:
			print(-1)
		else:
			print(max(cnth, cntl))


T = int(input())
D = [None] * 10000001
while T > 0:
	D1 = [0] * 10000001
	D2 = [0] * 10000001
	(N, Q) = input().strip().split(' ')
	(N, Q) = [int(N), int(Q)]
	A = list()
	A = list(map(int, input().strip().split(' ')))
	B = [None] * N
	E = [None] * N
	z = 0
	C = [None] * Q
	for i in range(0, N):
		B[i] = A[i]
	for i in range(0, Q):
		C[i] = int(input())
	B.sort()
	t = 0
	for i in range(0, N):
		x = A[i]
		low = 0
		high = N - 1
		flag = 0
		swapl = 0
		swapr = 0
		l1 = 0
		r1 = 0
		while high >= 0:
			mid = int((low + high) // 2)
			if A[mid] == x:
				break
			if A[mid] < x:
				if mid > i:
					if B[N - 1 - l1] > x:
						swapl = swapl + 1
					else:
						flag = 1
						break
					high = mid - 1
					l1 = l1 + 1
				else:
					low = mid + 1
					r1 = r1 + 1
			elif mid < i:
				if B[r1] < x:
					swapr = swapr + 1
				else:
					flag = 1
					break
				low = mid + 1
				r1 = r1 + 1
			else:
				high = mid - 1
				l1 = l1 + 1
		if l1 > 0 and B[N - l1] <= x:
			flag = 1
		if r1 > 0 and B[r1 - 1] >= x:
			flag = 1
		if x >= 10000000:
			x1 = x
			x = x % 10000000
			x1 = (x1 - x) // 10000000
			if D1[x] == 0:
				D1[x] = t * 100
				t = t + 1
			if flag == 0:
				if swapl > swapr:
					D2[x1 + D1[x]] = swapl
				else:
					D2[x1 + D1[x]] = swapr
			else:
				D2[x1 + D1[x]] = -1
		elif flag == 0:
			if swapl > swapr:
				D[x] = swapl
			else:
				D[x] = swapr
		else:
			D[x] = -1
	for i in range(0, Q):
		x = C[i]
		if x >= 10000000:
			x1 = x
			x = x % 10000000
			x1 = (x1 - x) // 10000000
			print(D2[x1 + D1[x]])
		else:
			print(D[x])
	T = T - 1


from bisect import bisect_left as bl

def bs(arr, less, idx, num):
	large = len(arr) - less - 1
	p = less
	low = 0
	high = len(a) - 1
	ans = 0
	(large_swap, less_swap) = (0, 0)
	while True:
		mid = (low + high) // 2
		if arr[mid] == num:
			return ans
		elif mid > idx and arr[mid] < num:
			if large <= 0 and less_swap <= 0:
				return -1
			elif less_swap:
				less_swap -= 1
				large -= 1
				high = mid - 1
				continue
			ans += 1
			large -= 1
			large_swap += 1
			high = mid - 1
		elif mid < idx and arr[mid] > num:
			if less <= 0 and large_swap <= 0:
				return -1
			elif large_swap:
				large_swap -= 1
				less -= 1
				low = mid + 1
				continue
			ans += 1
			less -= 1
			less_swap += 1
			low = mid + 1
		elif arr[mid] < num and mid < idx:
			if less <= 0 and large_swap <= 0:
				return -1
			less -= 1
			low = mid + 1
		elif arr[mid] > num and mid > idx:
			if large <= 0 and less_swap <= 0:
				return -1
			large -= 1
			high = mid - 1

def solve(a, num, arr):
	num_lesser = bl(a, num)
	num_idx = dic[num]
	return bs(arr, num_lesser, num_idx, num)
for i in range(int(input())):
	(n, q) = [int(x) for x in input().split()]
	arr = [int(x) for x in input().split()]
	dic = {}
	for i in range(n):
		dic[arr[i]] = i
	a = sorted(arr)
	for i in range(q):
		num = int(input())
		if n == 1:
			print(0)
			continue
		ans = solve(a, num, arr)
		print(ans)


def search(arr, l, r, x, index, small, SMALL, large, LARGE):
	mid = int((l + r) / 2)
	if index == mid:
		return (small, SMALL, large, LARGE)
	elif index < mid:
		if arr[mid] < x:
			large += 1
		else:
			LARGE += 1
		return search(arr, l, mid - 1, x, index, small, SMALL, large, LARGE)
	else:
		if arr[mid] < x:
			SMALL += 1
		else:
			small += 1
		return search(arr, mid + 1, r, x, index, small, SMALL, large, LARGE)

def SIndex_Index(Sorted, l, r, x):
	mid = int((l + r) / 2)
	if Sorted[mid][1] == x:
		return (mid, Sorted[mid][0])
	elif Sorted[mid][1] < x:
		return SIndex_Index(Sorted, mid + 1, r, x)
	else:
		return SIndex_Index(Sorted, l, mid - 1, x)
T = int(input())
for l in range(T):
	(N, Q) = input().split(' ')
	N = int(N)
	Q = int(Q)
	arr = input().split(' ')
	for p in range(N):
		arr[p] = int(arr[p])
	Sorted = sorted(enumerate(arr), key=lambda x: x[1])
	for k in range(Q):
		x = int(input())
		(SIndex, Index) = SIndex_Index(Sorted, 0, N - 1, x)
		(small, SMALL, large, LARGE) = search(arr, 0, N - 1, x, Index, 0, 0, 0, 0)
		leftS = SIndex - SMALL
		leftL = N - SIndex - 1 - LARGE
		if leftS >= small and leftL >= large:
			print(max(small, large))
		else:
			print(-1)


def Query(A, x, index, n, X):
	y = n - x - 1
	stepL = 0
	stepH = 0
	low = 0
	high = n - 1
	while low <= high:
		mid = (low + high) // 2
		if mid == index:
			break
		elif index > mid:
			low = mid + 1
			if A[mid] > X:
				if x > 0:
					stepL += 1
					x -= 1
				else:
					return -1
			elif x > 0:
				x -= 1
			else:
				return -1
		else:
			high = mid - 1
			if A[mid] < X:
				if y > 0:
					stepH += 1
					y -= 1
				else:
					return -1
			elif y > 0:
				y -= 1
			else:
				return -1
	return max(stepL, stepH)
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	A = list(map(int, input().split()))
	B = sorted(A)
	D1 = {}
	D2 = {}
	for i in range(n):
		D1[A[i]] = i
		D2[B[i]] = i
	for i in range(q):
		x = int(input())
		print(Query(A, D2[x], D1[x], n, x))


def bsc(a, di, dn, x, n):
	xi = dn[x]
	c = 0
	(s1, s2, l1, l2) = (0, 0, 0, 0)
	(l, h) = (0, n - 1)
	while l <= h:
		m = int((l + h) / 2)
		if a[m] == x:
			xj = di[x]
			if xj - s2 >= s1 and n - xj - 1 - l2 >= l1:
				return max(s1, l1)
			else:
				return -1
		elif a[m] < x and xi < m:
			l1 += 1
		elif a[m] > x and xi > m:
			s1 += 1
		elif a[m] > x and xi < m:
			l2 += 1
		elif a[m] < x and xi > m:
			s2 += 1
		if xi > m:
			(l, h) = (m + 1, h)
		else:
			(l, h) = (l, m - 1)
	xj = di[x]
	if xj - s2 >= s1 and n - xj - 1 - l2 >= l1:
		return max(s1, l1)
	else:
		return -1
t = int(input())
for i in range(t):
	n = input().split()
	(n, q) = (int(n[0]), int(n[1]))
	a = list(map(int, input().split()))
	l = list(a)
	l.sort()
	(di, dn) = (dict(), dict())
	for i in range(n):
		di[l[i]] = i
		dn[a[i]] = i
	for j in range(q):
		x = int(input())
		print(bsc(a, di, dn, x, n))


def main():
	T = int(input())
	for t in range(T):
		inp = input().split()
		N = int(inp[0])
		Q = int(inp[1])
		inp = input().split()
		A = [int(i) for i in inp]
		d = {}
		for i in range(N):
			d[A[i]] = i
		As = sorted(A)
		ds = {}
		for i in range(N):
			ds[As[i]] = i
		for q in range(Q):
			X = int(input())
			ind = d[X]
			low = 0
			high = N - 1
			gl = 0
			gg = 0
			lg = 0
			ll = 0
			while low <= high:
				mid = int((low + high) / 2)
				if mid == ind:
					break
				if mid > ind:
					if A[mid] < X:
						gl += 1
					else:
						gg += 1
					high = mid - 1
				else:
					if A[mid] > X:
						lg += 1
					else:
						ll += 1
					low = mid + 1
			swaps = min(lg, gl)
			l = ds[X]
			g = N - l - 1
			if lg > gl:
				if lg - gl <= l - ll - gl:
					print(swaps + lg - gl)
				else:
					print(-1)
			elif gl > lg:
				if gl - lg <= g - lg - gg:
					print(swaps + gl - lg)
				else:
					print(-1)
			else:
				print(swaps)
main()


import copy

def binsearch(l, x, n):
	low = 0
	high = n - 1
	while low <= high:
		mid = (low + high) // 2
		if l[mid][0] < x:
			low = mid + 1
		elif l[mid][0] > x:
			high = mid - 1
		else:
			break
	return mid

def fakebs(b, x, n, fakeindex, smallerElements, greaterElements):
	low = 0
	high = n - 1
	smallerswap = 0
	greaterswap = 0
	check = 0
	while low <= high:
		mid = (low + high) // 2
		if b[mid] < x:
			if fakeindex > mid:
				low = mid + 1
				smallerElements -= 1
			else:
				high = mid - 1
				greaterswap += 1
		elif b[mid] > x:
			if fakeindex < mid:
				high = mid - 1
				greaterElements -= 1
			else:
				low = mid + 1
				smallerswap += 1
		else:
			check = 1
			break
	if check == 0:
		return 1
	swaps = greaterswap - smallerswap
	if swaps > 0:
		greaterElements -= smallerswap
		smallerElements -= smallerswap
		if greaterElements >= swaps:
			swaps += smallerswap
		else:
			swaps = -1
	elif swaps < 0:
		swaps *= -1
		smallerElements -= greaterswap
		greaterElements -= greaterswap
		if smallerElements >= swaps:
			swaps += greaterswap
		else:
			swaps = -1
	else:
		swaps = greaterswap
	return swaps
t = int(input())
for i in range(t):
	(n, q) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	b = copy.deepcopy(a)
	l = []
	for k in range(n):
		l.append([a[k], k])
	l = sorted(l, key=lambda x: x[0])
	for j in range(q):
		x = int(input())
		ix = binsearch(l, x, n)
		fakeindex = l[ix][1]
		smallerElements = ix
		greaterElements = n - ix - 1
		print(fakebs(b, x, n, fakeindex, smallerElements, greaterElements))


indexdict = {}

def binsearch(key):
	(low, high) = (0, len(temp) - 1)
	while low <= high:
		mid = (low + high) // 2
		if temp[mid] == key:
			return mid
		elif temp[mid] < key:
			low = mid + 1
		else:
			high = mid - 1
	return None

def fakebinsearch(key):
	low = 0
	high = len(arr) - 1
	ind = indexdict[key]
	smaller = bigger = 0
	t = binsearch(key)
	(sm, lg) = (t, len(temp) - t - 1)
	while low <= high:
		mid = (low + high) // 2
		if mid == ind:
			break
		elif mid > ind:
			if arr[mid] < key:
				smaller += 1
			else:
				lg -= 1
			high = mid - 1
		else:
			if arr[mid] > key:
				bigger += 1
			else:
				sm -= 1
			low = mid + 1
	mn = min(smaller, bigger)
	sm -= mn
	lg -= mn
	diff = abs(smaller - bigger)
	if smaller == bigger:
		return smaller
	elif smaller > bigger:
		if lg >= diff:
			return smaller
		else:
			return -1
	elif sm >= diff:
		return bigger
	else:
		return -1
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	arr = list(map(int, input().split()))
	temp = sorted(arr)
	for i in range(n):
		indexdict[arr[i]] = i
	for _1 in range(q):
		x = int(input())
		print(fakebinsearch(x))


def bs(arr, n, x):
	low = 0
	high = n
	while low <= high:
		mid = (low + high) // 2
		if arr[mid] == x:
			break
		elif arr[mid] < x:
			low = mid + 1
		else:
			high = mid - 1
	return mid

def mbs(arr, n, x, ltX, oI):
	low = 0
	high = n
	acG = 0
	need2G = 0
	needG = 0
	needL = 0
	mtX = n - ltX
	swaps = 0
	while low <= high:
		mid = (low + high) // 2
		if arr[mid] == x:
			break
		elif arr[mid] < x and oI < mid:
			needG += 1
			need2G += 1
			high = mid - 1
			swaps += 1
		elif arr[mid] < x:
			low = mid + 1
			needL += 1
		elif arr[mid] > x and oI > mid:
			acG += 1
			needL += 1
			low = mid + 1
			swaps += 1
		else:
			high = mid - 1
			needG += 1
	interior_swaps = min(need2G, acG)
	if needG > mtX or needL > ltX:
		return -1
	else:
		return swaps - interior_swaps
for i in range(int(input())):
	(n, q) = list(map(int, input().split()))
	arr = []
	arr2 = []
	d = dict()
	arr = list(map(int, input().split()))
	arr2 = list(arr)
	for i1 in range(n):
		d[arr[i1]] = i1
	arr2.sort()
	for k in range(q):
		x = int(input())
		oI = d[x]
		nltX = bs(arr2, n - 1, x)
		print(mbs(arr, n - 1, x, nltX, oI))


def fakebfs(orig_array, sorted_array, indices, sorted_indices, x, n, index):
	index_in_sorted = sorted_indices[x]
	small = index_in_sorted - 1
	large = index_in_sorted + 1
	low = 0
	high = n - 1
	count = 0
	num_greater = 0
	num_lesser = 0
	while low <= high:
		mid = int((low + high) / 2)
		elem = orig_array[mid]
		if elem == x:
			if small < -1:
				print(-1)
				break
			if large > n:
				print(-1)
				break
			print(max(num_lesser, num_greater))
			break
		if index > mid:
			low = mid + 1
			if elem < x:
				small -= 1
				pass
			elif small > -1:
				small -= 1
				num_lesser += 1
			else:
				small -= 1
				pass
		else:
			high = mid - 1
			if elem > x:
				large += 1
				pass
			elif large < n:
				num_greater += 1
				large += 1
			else:
				large += 1
				pass
test = int(input())
for t in range(test):
	(n, q) = map(int, input().split())
	orig_array = list(map(int, input().split()))
	sorted_array = orig_array[:]
	sorted_array.sort()
	indices = dict()
	sorted_indices = dict()
	for i in range(len(sorted_array)):
		indices[orig_array[i]] = i
		sorted_indices[sorted_array[i]] = i
	for i in range(q):
		x = int(input())
		fakebfs(orig_array, sorted_array, indices, sorted_indices, x, n, indices[x])


from copy import *
t = int(input())
for i in range(t):
	yoar = list(map(int, input().split()))
	n = yoar[0]
	q = yoar[1]
	arr = list(map(int, input().split()))
	dic = {}
	for j in range(n):
		dic[arr[j]] = j
	sorarr = deepcopy(arr)
	sorarr.sort()
	dic1 = {}
	for j in range(n):
		dic1[sorarr[j]] = j
	for j in range(q):
		x = int(input())
		if x not in dic:
			print(0)
			continue
		ind = dic[x]
		ind1 = dic1[x]
		leftcont = ind1
		rightcount = n - ind1 - 1
		low = 0
		high = n - 1
		countbig = 0
		countsmall = 0
		ans = 0
		while low <= high:
			mid = (low + high) // 2
			if mid == ind:
				break
			elif mid < ind:
				if arr[mid] > x:
					countsmall += 1
				else:
					leftcont = leftcont - 1
				low = mid + 1
			elif mid > ind:
				if arr[mid] < x:
					countbig += 1
				else:
					rightcount = rightcount - 1
				high = mid - 1
		if countbig > rightcount:
			ans = -1
		elif countsmall > leftcont:
			ans = -1
		else:
			ans = max(countbig, countsmall)
		print(ans)


def f(a, y, index, sorted_pos):
	n = len(a)
	low = 0
	high = n - 1
	(L, R) = (0, 0)
	(l, r) = (0, 0)
	while low <= high:
		mid = (low + high) // 2
		if a[mid] == y:
			break
		elif mid > index[y]:
			high = mid - 1
			L += 1
			if a[mid] < y:
				l += 1
		else:
			low = mid + 1
			R += 1
			if a[mid] > y:
				r += 1
	x = sorted_pos[y]
	if R > x or L > n - x - 1:
		print('-1')
	else:
		print(max(l, r))

def fun():
	test = int(input())
	for t in range(test):
		(n, q) = list(map(int, input().split()))
		arr = list(map(int, input().split()))
		index = dict()
		for i in range(n):
			index[arr[i]] = i
		sorted_pos = dict()
		a = sorted(arr)
		for i in range(n):
			sorted_pos[a[i]] = i
		for x in range(q):
			y = int(input())
			f(arr, y, index, sorted_pos)
fun()


t = int(input())
while t != 0:
	t -= 1
	(n, q) = [int(x) for x in input().strip().split()]
	a = [int(x) for x in input().strip().split()]
	sorted_a = sorted(a)
	indexOf = {}
	index = 0
	for ele in a:
		indexOf[ele] = index
		index += 1
	index = 0
	countlessthan = {}
	countgreaterthan = {}
	for ele in sorted_a:
		countlessthan[ele] = index
		countgreaterthan[ele] = n - 1 - index
		index += 1
	while q != 0:
		q = q - 1
		x = int(input())
		low = 0
		high = n - 1
		swapGreaterYes = 0
		swapGreaterNo = 0
		swapLesserYes = 0
		swapLesserNo = 0
		while low <= high:
			mid = (low + high) // 2
			if a[mid] == x:
				break
			elif a[mid] < x and indexOf[x] > mid:
				low = mid + 1
				swapLesserNo += 1
			elif a[mid] < x and indexOf[x] < mid:
				high = mid - 1
				swapGreaterYes += 1
			elif a[mid] > x and indexOf[x] < mid:
				swapGreaterNo += 1
				high = mid - 1
			elif a[mid] > x and indexOf[x] > mid:
				swapLesserYes += 1
				low = mid + 1
		neededswaps = max(swapLesserYes, swapGreaterYes)
		ans = neededswaps
		if swapLesserYes > countlessthan[x] - swapLesserNo or swapGreaterYes > countgreaterthan[x] - swapGreaterNo:
			ans = -1
		else:
			ans = neededswaps
		print(ans)


def binary(a, n, x):
	low = 0
	high = n - 1
	pos = 0
	while low <= high:
		mid = (low + high) // 2
		if a[mid] == x:
			pos = 1
			break
		elif a[mid] < x:
			low = mid + 1
		else:
			high = mid - 1
	return (mid, pos)

def spbinary(a, a1, n, x, x1):
	low = 0
	high = n - 1
	small = []
	great = []
	cs = 0
	cg = 0
	cis = 0
	cig = 0
	while low <= high:
		mid = (low + high) // 2
		if a[mid] == x:
			pos = 1
			break
		elif a[mid] < x:
			low = mid + 1
			if a1[mid] < x1:
				cis += 1
			else:
				cs += 1
		else:
			high = mid - 1
			if a1[mid] > x1:
				cig += 1
			else:
				cg += 1
	return (cg, cs, cig, cis)
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	s = []
	for i in range(1, n + 1):
		s.append(i)
	a = list(map(int, input().split()))
	d = {}
	index = []
	sorte = sorted(a)
	dsorte = {}
	for i in range(n):
		d[a[i]] = i
		index.append(i)
		dsorte[sorte[i]] = i
	for b in range(q):
		x = int(input())
		(mid, pos) = binary(a, n, x)
		if pos == 1:
			print(0)
		else:
			ptr = d[x]
			smaller = []
			greater = []
			(cg, cs, cig, cis) = spbinary(index, a, n, ptr, x)
			big = n - dsorte[x] - 1
			less = dsorte[x]
			big -= cig
			less -= cis
			if less >= cs and big >= cg:
				if max(cs, cg) <= min(less, big):
					res = max(cs, cg)
					print(res)
				else:
					print('-1')
			else:
				print('-1')


t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	b = []
	b1 = {}
	for y in range(q):
		k = int(input())
		b.append(k)
		b1[k] = [0, 0]
	for i in range(n):
		if a[i] in b1:
			b1[a[i]][0] = i
	p = a.copy()
	p.sort()
	for i in range(n):
		if p[i] in b1:
			b1[p[i]][1] = i
	for i in range(q):
		s = b1[b[i]][1]
		pos = b1[b[i]][0]
		e = n - s - 1
		l = 0
		r = n - 1
		s1 = 0
		e1 = 0
		s2 = 0
		e2 = 0
		while l <= r:
			m = (l + r) // 2
			if m == pos:
				break
			elif m < pos:
				s1 += 1
				if a[m] > a[pos]:
					s2 += 1
				l = m + 1
			else:
				e1 += 1
				if a[m] < a[pos]:
					e2 += 1
				r = m - 1
		if s1 <= s and e1 <= e:
			print(max(s2, e2))
		else:
			print(-1)


t = int(input())
for i in range(t):
	y = [int(i) for i in input().split()]
	n = y[0]
	q = y[1]
	a = [int(j) for j in input().split()]
	b = sorted(a)
	dic = {}
	dic1 = {}
	for j in range(n):
		dic[a[j]] = j
	for j in range(n):
		dic1[b[j]] = j
	for j in range(q):
		x = int(input())
		ind = dic[x] + 1
		low = 1
		high = n
		small = 0
		sdone = 0
		ldone = 0
		large = 0
		while low <= high:
			mid = (low + high) // 2
			if mid == ind:
				break
			elif mid < ind:
				small += 1
				if a[mid - 1] < a[ind - 1]:
					sdone += 1
				low = mid + 1
			else:
				large += 1
				if a[mid - 1] > a[ind - 1]:
					ldone += 1
				high = mid - 1
		shave = dic1[x]
		lhave = n - dic1[x] - 1
		if small <= shave and large <= lhave:
			print(max(small - sdone, large - ldone))
		else:
			print(-1)


for t in range(int(input())):
	(n, q) = [int(x) for x in input().strip().split()]
	a = [int(x) for x in input().strip().split()]
	d = {ai: i for (i, ai) in enumerate(a)}
	b = {ai: i for (i, ai) in enumerate(sorted(a))}
	for query in range(q):
		x = int(input())
		need_above = 0
		need_below = 0
		used_above = 0
		used_below = 0
		low = 1
		high = n
		while True:
			mid = (low + high) // 2
			if a[mid - 1] == x:
				break
			elif a[mid - 1] < x:
				if d[x] > mid - 1:
					low = mid + 1
					used_below += 1
				else:
					high = mid - 1
					need_above += 1
			elif d[x] > mid - 1:
				low = mid + 1
				need_below += 1
			else:
				high = mid - 1
				used_above += 1
		if need_below + used_below > b[x] or need_above + used_above > n - 1 - b[x]:
			print(-1)
		else:
			print(max(need_below, need_above))


def bs(l, x, i, n, si):
	low = 1
	high = n
	lc = 0
	gc = 0
	l1 = 0
	g1 = 0
	mid = (low + high) // 2
	while mid != i:
		if i > mid:
			l1 = l1 + 1
			low = mid + 1
			if l[mid] > x:
				lc = lc + 1
		if i < mid:
			g1 = g1 + 1
			high = mid - 1
			if l[mid] < x:
				gc = gc + 1
		mid = (low + high) // 2
	g1 = g1 - (n - si - 1)
	l1 = l1 - si
	if g1 > 0 or l1 > 0:
		return -1
	else:
		return max(lc, gc)
t = int(input())
for k in range(t):
	r = input().split()
	n = int(r[0])
	q = int(r[1])
	l = [int(x) for x in input().split()]
	l.insert(0, -1000)
	d1 = {}
	for i in range(1, n + 1):
		d1[l[i]] = i
	s = l[0:n + 1]
	s.sort()
	d2 = {}
	for i in range(1, n + 1):
		d2[s[i]] = i
	for j in range(q):
		x = int(input())
		index = d1[x]
		print(bs(l, x, index, n, d2[x] - 1))


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	hm1 = {}
	arr = []
	brr = []
	arr = list(map(int, input().split()))
	brr = arr[:]
	brr.sort()
	for i in range(n):
		hm1[arr[i]] = [0, 0]
	for i in range(n):
		hm1[arr[i]][0] = i
		hm1[brr[i]][1] = i
	for i in range(q):
		inp = int(input())
		x = hm1[inp][0]
		st = 0
		en = n - 1
		count = 0
		al = []
		while st <= en:
			mid = (en + st) // 2
			al.append(mid)
			if mid == x:
				break
			elif x > mid:
				st = mid + 1
			else:
				en = mid - 1
		al.sort()
		val1 = arr[x]
		ind1 = hm1[val1][1]
		ind2 = 0
		flag = 0
		c1 = 0
		c2 = 0
		for j in range(len(al)):
			if arr[al[j]] == val1:
				ind2 = j
				flag = 1
				continue
			if flag == 0 and arr[al[j]] > val1:
				c1 += 1
			elif flag == 1 and arr[al[j]] < val1:
				c2 += 1
		if c1 > c2:
			count += c1
		else:
			count += c2
		if ind1 >= ind2 and len(arr) - ind1 >= len(al) - ind2:
			print(count)
		else:
			print(-1)


def path(arr, n, x):
	l = 0
	h = n - 1
	left = []
	right = []
	while l <= h:
		m = (l + h) // 2
		if arr[m] == x:
			break
		elif arr[m] > x:
			left.append(arr[m])
			h = m - 1
		else:
			right.append(arr[m])
			l = m + 1
	return (left, right)
t = int(input())
for z in range(t):
	l = [int(a) for a in input().split()]
	n = l[0]
	q = l[1]
	ad = [int(s) for s in input().split()]
	arr = [-1] * n
	dict2 = {}
	b = sorted(ad)
	for i in range(n):
		dict2[b[i]] = i
		arr[i] = i
	swaps = [-1] * n
	for i in range(n):
		x = ad[i]
		pos = i
		ps = dict2[x]
		pl = ps
		ph = n - 1 - ps
		l = 0
		h = n - 1
		kl = 0
		kh = 0
		can = 1
		(left, right) = path(arr, n, pos)
		nl = len(left)
		nr = len(right)
		if nl > ph or nr > pl:
			can = 0
		while l <= h:
			m = (l + h) // 2
			if pos == m:
				break
			if pos > m:
				if x < ad[m]:
					kl += 1
				l = m + 1
			else:
				if x > ad[m]:
					kh += 1
				h = m - 1
		if can == 0:
			swaps[ps] = -1
		else:
			swaps[ps] = kh + kl - min(kh, kl)
	for y in range(q):
		z = int(input())
		print(swaps[dict2[z]])


t = int(input())
for i in range(t):
	a = input()
	b = a.split()
	n = int(b[0])
	q = int(b[1])
	c = input()
	d = c.split()
	e = {}
	ff = []
	for j in range(n):
		d[j] = int(d[j])
		ff.append(int(d[j]))
		e[int(d[j])] = j
	d.sort()
	g = {}
	for l in range(n):
		g[int(d[l])] = l
	for k in range(q):
		f = int(input())
		low = 0
		high = n - 1
		swaps = 0
		s1 = 0
		s2 = 0
		o = 0
		big = n - g[f] - 1
		small = g[f]
		p = 0
		while low <= high:
			mid = (low + high) // 2
			if mid == e[f]:
				break
			elif ff[mid] > f and e[f] < mid:
				big -= 1
				high = mid - 1
			elif ff[mid] < f and mid < e[f]:
				small -= 1
				low = mid + 1
			elif ff[mid] > f and e[f] > mid:
				s1 += 1
				low = mid + 1
			elif ff[mid] < f and e[f] < mid:
				s2 += 1
				high = mid - 1
		swaps = min(s1, s2) + (max(s1, s2) - min(s1, s2))
		if swaps <= min(small, big):
			print(swaps)
		else:
			print(-1)


def bin(arr, x, l, r):
	while l <= r:
		mid = (r + l) // 2
		if arr[mid] == x:
			return mid
		elif arr[mid] < x:
			l = mid + 1
		else:
			r = mid - 1

def sol(index, sindex, arr, l, r, x):
	count1 = 0
	count2 = 0
	smr = 0
	gtr = 0
	smlr = sindex - l
	grtr = r - sindex
	while l <= r:
		mid = (r + l) // 2
		if mid == index:
			break
		elif mid < index:
			if arr[mid] > x:
				count1 += 1
			else:
				smr += 1
			l = mid + 1
		else:
			if arr[mid] < x:
				count2 += 1
			else:
				gtr += 1
			r = mid - 1
	if count1 + smr <= smlr and count2 + gtr <= grtr:
		print(max(count2, count1))
	else:
		print(-1)
t = int(input())
for i in range(t):
	(N, Q) = map(int, input().split())
	a = list(map(int, input().split()))
	k = list(a)
	index = list(sorted(range(len(a)), key=lambda x: a[x]))
	list.sort(a)
	for j in range(Q):
		x = int(input())
		q = bin(a, x, 0, N - 1)
		z = index[q]
		sol(z, q, k, 0, N - 1, x)


t = int(input())
for _ in range(t):
	(n, q) = input().split()
	n = int(n)
	q = int(q)
	a = list(map(int, input().split()))
	b = list(a)
	b.sort()
	d = {}
	small = {}
	big = {}
	for i in range(n):
		d[a[i]] = i
		small[b[i]] = i
		big[b[i]] = n - i - 1
	for test in range(q):
		x = int(input())
		low = 0
		high = n - 1
		count_small = 0
		count_big = 0
		check_small = 0
		check_big = 0
		flag = 0
		while low <= high:
			mid = (low + high) // 2
			if a[mid] == x:
				break
			elif x > a[mid] and d[x] > d[a[mid]]:
				if small[x] > check_small:
					check_small += 1
					low = mid + 1
				else:
					flag = 1
					break
			elif x < a[mid] and d[x] < d[a[mid]]:
				if big[x] > check_big:
					check_big += 1
					high = mid - 1
				else:
					flag = 1
					break
			elif x > a[mid] and d[x] < d[a[mid]]:
				if big[x] > check_big:
					high = mid - 1
					count_big += 1
					check_big += 1
				else:
					flag = 1
					break
			elif x < a[mid] and d[x] > d[a[mid]]:
				if small[x] > check_small:
					low = mid + 1
					count_small += 1
					check_small += 1
				else:
					flag = 1
					break
		if flag == 1:
			print('-1')
		else:
			print(max(count_big, count_small))


def bs(a, n, x):
	low = 0
	high = n - 1
	while low <= high:
		mid = (low + high) // 2
		if a[mid] == x:
			break
		elif a[mid] < x:
			low = mid + 1
		else:
			high = mid - 1
	return mid
t = int(input())
for _ in range(t):
	(n, q) = input().split()
	n = int(n)
	q = int(q)
	a = list(map(int, input().split()))
	arr = list()
	for i in range(n):
		al = list()
		al.append(a[i])
		al.append(i)
		arr.append(al)
	b = list(a)
	b.sort()
	barr = list(arr)
	barr.sort(key=lambda barr: barr[0])
	for p in range(q):
		qu = int(input())
		index_sorted = bs(b, n, qu)
		s = index_sorted
		os = s
		l = n - s - 1
		ol = l
		index_unsorted = barr[index_sorted][1]
		low = 0
		high = n - 1
		flag = 0
		sc = lc = 0
		mid = (low + high) // 2
		while low <= high:
			if s == -1 or l == -1:
				flag = 1
				break
			mid = (low + high) // 2
			if mid == index_unsorted:
				break
			elif mid < index_unsorted:
				if a[mid] > qu:
					sc = sc + 1
				s = s - 1
				low = mid + 1
			else:
				if a[mid] < qu:
					lc = lc + 1
				l = l - 1
				high = mid - 1
		if flag == 1:
			print(-1)
		elif sc > lc:
			print(sc)
		else:
			print(lc)


from sys import stdin

def binary_count(a, dorg, dinc, n, x):
	low = 0
	high = n - 1
	smalln = dinc[x]
	bign = n - 1 - dinc[x]
	smallu = 0
	bigu = 0
	pos = dorg[x]
	while low <= high:
		mid = (low + high) // 2
		if mid == pos:
			return max(bigu, smallu)
		elif a[mid] < x:
			if mid < pos:
				if smalln > 0:
					low = mid + 1
					smalln -= 1
				else:
					break
			elif bign > 0:
				bigu += 1
				bign -= 1
				high = mid - 1
			else:
				break
		elif mid > pos:
			if bign > 0:
				high = mid - 1
				bign -= 1
			else:
				break
		elif smalln > 0:
			smallu += 1
			smalln -= 1
			low = mid + 1
		else:
			break
	return -1
for _ in range(int(stdin.readline().strip())):
	(n, q) = tuple(map(int, stdin.readline().split()))
	a = list(map(int, stdin.readline().split()))
	x = [int(stdin.readline().strip()) for i in range(q)]
	da = {n: i for (i, n) in enumerate(a)}
	a2 = sorted(a)
	d2 = {n: i for (i, n) in enumerate(a2)}
	print('\n'.join([str(binary_count(a, da, d2, n, c)) for c in x]))


def binarySearchMain(sm, value, num):
	l = 0
	r = num - 1
	m = 0
	while l <= r:
		m = (l + r) // 2
		if sm[m] == value:
			return m
		elif sm[m] > value:
			r = m - 1
		elif sm[m] < value:
			l = m + 1

def binarySearch(value, num):
	l = 0
	r = num - 1
	countL = 0
	countR = 0
	rightL = 0
	rightR = 0
	while l <= r:
		m = (l + r) // 2
		if m + 1 == value:
			break
		elif m + 1 > value:
			if array[m] > qi:
				rightL += 1
			countL += 1
			r = m - 1
		elif m + 1 < value:
			if array[m] < qi:
				rightR += 1
			countR += 1
			l = m + 1
	return [countL, countR, rightL, rightR]
tc = int(input())
while tc > 0:
	(n, q) = map(int, input().split())
	array = list(map(int, input().split()))
	d = {}
	for k in range(n):
		d[array[k]] = k + 1
	array2 = sorted(array)
	if n <= 10:
		pos1 = -1
		while q > 0:
			qi = int(input())
			pos1 = d[qi]
			a = binarySearch(pos1, n)
			flag = 1
			i = binarySearchMain(array2, qi, n)
			if a[0] > n - i - 1 or a[2] > n - i - 1 or a[1] > i or (a[3] > i):
				flag = 0
			if flag == 0:
				print(-1)
			else:
				print(max(a[0] - a[2], a[1] - a[3]))
			q -= 1
	else:
		pos = -1
		while q > 0:
			qi = int(input())
			pos1 = d[qi]
			a = binarySearch(pos1, n)
			flag = 1
			i = binarySearchMain(array2, qi, n)
			if a[0] > n - i - 1 or a[2] > n - i - 1 or a[1] > i or (a[3] > i):
				flag = 0
			if flag == 0:
				print(-1)
			else:
				print(max(a[0] - a[2], a[1] - a[3]))
			q -= 1
	tc -= 1


for i in range(int(input())):
	(n, q) = map(int, input().split())
	l = list(map(int, input().split()))
	d2 = {}
	for j in range(n):
		d2[l[j]] = j
	arr = list(l)
	arr.sort()
	d1 = {}
	for j in range(n):
		d1[arr[j]] = j
	for j in range(q):
		x = int(input())
		(g1, g3, l1, l3, start, end, index) = (0, 0, 0, 0, 0, n - 1, d2[x])
		while start <= end:
			mid = (start + end) // 2
			if mid == index:
				break
			elif index > mid:
				if l[mid] > x:
					l3 += 1
					g1 += 1
				else:
					l1 += 1
				start = mid + 1
			else:
				if l[mid] > x:
					g1 += 1
				else:
					l1 += 1
					g3 += 1
				end = mid - 1
		g2 = n - 1 - d1[x] - g1
		l2 = d1[x] - l1
		ans = 0
		f = 0
		if g3 > 0 and l3 > 0:
			x = min(g3, l3)
			g3 -= x
			l3 -= x
			ans += x
		if g3 > 0:
			if g3 > g2:
				f = 1
			else:
				ans += g3
		if l3 > 0:
			if l3 > l2:
				f = 1
			else:
				ans += l3
		if f == 0:
			print(ans)
		else:
			print(-1)


T = int(input())
for xs in range(T):
	(N, Q) = [int(o) for o in input().split()]
	a = [int(o) for o in input().split()]
	b = sorted(a)
	Di = {}
	for i in range(len(a)):
		Di[a[i]] = [i]
	for i in range(len(b)):
		Di[b[i]].append(i)
	r = []
	qu = [int(input()) for j in range(Q)]
	for q in qu:
		low = 1
		high = N
		ind = Di[q][0] + 1
		b = []
		f = []
		s = 0
		maxs = N - Di[q][1] - 1
		mins = N - maxs - 1
		while low <= high:
			mid = (low + high) // 2
			if mid == ind:
				break
			elif mid < ind:
				low = mid + 1
				if a[mid - 1] > q:
					b.append(a[mid - 1])
				else:
					mins -= 1
			elif mid > ind:
				high = mid - 1
				if a[mid - 1] < q:
					f.append(a[mid - 1])
				else:
					maxs -= 1
		lenf = len(f)
		lenb = len(b)
		sw = min(lenf, lenb)
		rs = max(lenf, lenb) - sw
		(mins, maxs) = (mins - sw, maxs - sw)
		ex = min(mins, maxs)
		if ex < rs:
			r.append(-1)
			s = 1
		else:
			sw += rs
		if not s:
			r.append(sw)
	for ans in r:
		print(ans)


def BSearch(array, n, x):
	low = 0
	high = n - 1
	while low <= high:
		mid = (low + high) // 2
		if array[mid] == x:
			break
		elif array[mid] < x:
			low = mid + 1
		else:
			high = mid - 1
	return mid

def indexSearch(array, n, i, less, more):
	low = 0
	high = n - 1
	lessbad = 0
	morebad = 0
	while low <= high:
		mid = (low + high) // 2
		if mid == i:
			break
		elif mid < i:
			if array[mid] < array[i]:
				less -= 1
			else:
				morebad += 1
			low = mid + 1
		else:
			if array[mid] > array[i]:
				more -= 1
			else:
				lessbad += 1
			high = mid - 1
	if lessbad == morebad:
		return lessbad
	elif lessbad < morebad:
		if less >= morebad:
			return morebad
		else:
			return -1
	elif more >= lessbad:
		return lessbad
	else:
		return -1
T = int(input())
for i in range(T):
	(N, Q) = map(int, input().split())
	Alist = list(map(int, input().split()))
	index = []
	for j in range(N):
		index.append(j)
	Asorted = list(Alist)
	(Asorted, index) = (list(x) for x in zip(*sorted(zip(Asorted, index))))
	for j in range(Q):
		X = int(input())
		a = BSearch(Asorted, N, X)
		inda = index[a]
		less1 = a
		more1 = N - a - 1
		ans = indexSearch(Alist, N, inda, less1, more1)
		print(ans)


import copy

def binary_search(a, n, x):
	low = 1
	high = n
	mid = (low + high) / 2
	mid = int(mid)
	swpl = 0
	swph = 0
	cntl = 0
	cnth = 0
	while low <= high:
		mid = (low + high) / 2
		mid = int(mid)
		if mid == x:
			break
		elif mid < x:
			low = mid + 1
			cntl = cntl + 1
			if a[mid] >= a[x]:
				swpl = swpl + 1
		else:
			high = mid - 1
			cnth = cnth + 1
			if a[mid] < a[x]:
				swph = swph + 1
	ss = [swpl, swph, cntl, cnth]
	return ss
T = int(input())
for i1 in range(T):
	arr = input()
	lo = list(map(int, arr.split()))
	n = lo[0]
	q = lo[1]
	arr1 = input()
	l1 = list(map(int, arr1.split()))
	a = 0
	l1 = [a] + l1
	l2 = copy.deepcopy(l1)
	d = dict()
	for i in range(1, n + 1):
		d[l2[i]] = i
	l1.sort()
	d1 = dict()
	for z in range(1, n + 1):
		d1[l1[z]] = z - 1
	for isa in range(q):
		k = int(input())
		k_pos = d[k]
		pp = binary_search(l2, n, k_pos)
		if pp[2] > d1[k] or pp[3] > n - 1 - d1[k]:
			print(-1)
		else:
			print(max(pp[0], pp[1]))


import copy
t = int(input())
for j in range(t):
	ans = []
	inp = input().split()
	n = int(inp[0])
	q = int(inp[1])
	arr = input().split()
	arr = [int(x) for x in arr]
	sorted = copy.deepcopy(arr)
	sorted.sort()
	index = {}
	sortedIndex = {}
	for i in range(n):
		index[arr[i]] = i
		sortedIndex[sorted[i]] = i
	for i in range(q):
		up = 0
		down = 0
		left = 0
		right = 0
		ele = int(input())
		low = 0
		high = n - 1
		while low < high:
			mid = int((low + high) / 2)
			if arr[mid] == ele:
				break
			if arr[mid] > ele and mid < index[ele]:
				up += 1
				low = mid + 1
			elif arr[mid] > ele and mid > index[ele]:
				high = mid - 1
				right += 1
			elif arr[mid] < ele and mid < index[ele]:
				left += 1
				low = mid + 1
			elif arr[mid] < ele and mid > index[ele]:
				high = mid - 1
				down += 1
		if up > down:
			if up + left <= sortedIndex[ele]:
				ans.append(up)
			else:
				ans.append(-1)
		elif down > up:
			if down + right <= n - 1 - sortedIndex[ele]:
				ans.append(down)
			else:
				ans.append(-1)
		else:
			ans.append(down)
	for i in range(q):
		print(ans[i])


def binarySearch(start, end, xindex, opList):
	if start <= end:
		midindex = int((start + end) / 2)
		opList.append(midindex)
		if xindex < midindex:
			return binarySearch(start, midindex - 1, xindex, opList)
		elif xindex > midindex:
			return binarySearch(midindex + 1, end, xindex, opList)
		else:
			return opList

def counter(opList, a, x):
	small = 0
	big = 0
	rightSmall = 0
	rightBig = 0
	for i in range(len(opList) - 1):
		if opList[i] < opList[i + 1]:
			if x < a[opList[i]]:
				small += 1
			else:
				rightSmall += 1
		elif x > a[opList[i]]:
			big += 1
		else:
			rightBig += 1
	flag = isBigSmallAvailable(small, big, x, a, rightBig, rightSmall)
	if flag:
		total = small + big
		total = total - min(small, big)
		return total
	else:
		return -1

def isBigSmallAvailable(small, big, x, a, rightBig, rightSmall):
	s = 0
	b = 0
	for i in range(len(a)):
		if a[i] < x:
			s += 1
		if a[i] > x:
			b += 1
	s = s - rightSmall
	b = b - rightBig
	if s >= small and b >= big:
		return True
	return False
t = int(input())
swapCount = 0
swaped = []
visited = []
for z in range(t):
	l = list(map(int, input().split()))
	n = int(l[0])
	q = int(l[1])
	aa = list(map(int, input().split()))
	for i in range(q):
		swapCount = 0
		swaped.clear()
		visited.clear()
		a = aa[:]
		x = int(input())
		xindex = a.index(x)
		opList = []
		result = binarySearch(0, n - 1, xindex, opList)
		count = counter(opList, a, x)
		print(count)


t = int(input())
while t > 0:
	t -= 1
	(n, q) = map(int, input().split())
	arr = list(map(int, input().split()))
	tarr = sorted(arr)
	d = {}
	inddir = {}
	for i in range(len(arr)):
		inddir[arr[i]] = i
	tarrlen = len(tarr)
	for i in range(len(tarr)):
		d[tarr[i]] = [i, tarrlen - i - 1]
	for _ in range(q):
		k = int(input())
		find = inddir[k]
		(l, r) = (1, tarrlen)
		gs = 0
		ls = 0
		sw = 0
		tempc = d[k].copy()
		while l <= r:
			mid = (l + r) // 2
			if mid - 1 == find:
				break
			elif mid - 1 < find:
				if arr[mid - 1] < k:
					if tempc[0] > 0:
						tempc[0] -= 1
					else:
						sw = -1
						break
				elif tempc[0] > 0:
					tempc[0] -= 1
					sw += 1
					ls += 1
				else:
					sw = -1
					break
				l = mid + 1
			else:
				if arr[mid - 1] > k:
					if tempc[1] > 0:
						tempc[1] -= 1
					else:
						sw = -1
						break
				elif tempc[1] > 0:
					tempc[1] -= 1
					sw += 1
					gs += 1
				else:
					sw = -1
					break
				r = mid - 1
		print(max(ls, gs) if sw != -1 else -1)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	b = []
	for i in a:
		b.append(i)
	b.sort()
	les = {}
	p = 0
	for i in b:
		les[i] = p
		p += 1
	di = {}
	for i in range(n):
		di[a[i]] = i
	for i in range(q):
		x = int(input())
		(k1, k2, k3, k4) = (0, 0, 0, 0)
		actual = di[x]
		start = 0
		end = n - 1
		while start < end:
			mid = (start + end) // 2
			if mid == actual:
				break
			elif mid < actual:
				if a[mid] > x:
					k1 += 1
				else:
					k3 += 1
				start = mid + 1
			else:
				if a[mid] < x:
					k2 += 1
				else:
					k4 += 1
				end = mid - 1
		k = max(k1, k2)
		if k1 > les[x] - k3 or k2 > n - les[x] - 1 - k4:
			k = -1
		print(k)


def minswaps(A, A2, D, n, x):
	(g, s, cg, cs) = (0, 0, 0, 0)
	(si, li) = (0, n - 1)
	while si <= li:
		mid = (si + li) // 2
		if mid == D[x]:
			break
		elif mid < D[x]:
			if A[mid] < x:
				cg += 1
			g += 1
			si = mid + 1
		else:
			if A[mid] > x:
				cs += 1
			s += 1
			li = mid - 1
	smaller = A2[x]
	larger = n - A2[x] - 1
	if s - cs == g - cg:
		return s - cs
	elif s - cs > g - cg:
		if larger - cs >= s - cs:
			return s - cs
		else:
			return -1
	elif smaller - cg >= g - cg:
		return g - cg
	else:
		return -1

def solve():
	(n, q) = map(int, input().split())
	A = list(map(int, input().split()))
	A2 = sorted(A)
	Dict1 = {}
	Dict2 = {}
	for i in range(n):
		Dict1[A[i]] = i
	for j in range(n):
		Dict2[A2[j]] = j
	for que in range(q):
		Q = int(input())
		ans = minswaps(A, Dict2, Dict1, n, Q)
		print(ans)
t = int(input())
for _ in range(t):
	solve()


def binary_search(a, n, x):
	low = 0
	high = n - 1
	while low <= high:
		mid = (low + high) // 2
		if a[mid][0] == x:
			break
		elif a[mid][0] < x:
			low = mid + 1
		else:
			high = mid - 1
	return mid

def fake_binary_search(a, b, n, x):
	low = 0
	high = n - 1
	swap = 0
	swap1 = 0
	swap2 = 0
	t2 = binary_search(b, n, x)
	t1 = t2
	t = b[t2][1]
	while low <= high:
		mid = (low + high) // 2
		if a[mid][0] == x:
			break
		elif a[mid][0] < x:
			if mid > t:
				if swap2 > 0:
					swap2 -= 1
				else:
					swap += 1
					swap1 += 1
				high = mid - 1
			else:
				t2 -= 1
				low = mid + 1
		elif mid < t:
			if swap1 > 0:
				swap1 -= 1
			else:
				swap2 += 1
				swap += 1
			low = mid + 1
		else:
			t1 += 1
			high = mid - 1
	if swap > t2 or swap > n - 1 - t1:
		swap = -1
	return swap
for _ in range(int(input())):
	(n, q) = map(int, input().split())
	A = list(map(int, input().split()))
	for i in range(n):
		A[i] = [A[i], i]
	B = sorted(A)
	for i in range(q):
		x = int(input())
		print(fake_binary_search(A, B, n, x))


T = int(input())
for i in range(T):
	(N, Q) = list(map(int, input().split()))
	nums = list(map(int, input().split()))
	sorted_nums = sorted(nums)
	sorted_index_map = {}
	index_map = {}
	for ind in range(N):
		sorted_index_map[sorted_nums[ind]] = ind
		index_map[nums[ind]] = ind
	for j in range(Q):
		X = int(input())
		index_X = index_map[X]
		low = 0
		high = N - 1
		count_low_needed = 0
		count_high_needed = 0
		count_low_minus = 0
		count_high_minus = 0
		total = 0
		while low <= high:
			mid = int((low + high) / 2)
			if nums[mid] == X:
				break
			elif index_X > mid:
				if nums[mid] > X:
					count_low_needed += 1
				else:
					count_low_minus += 1
				low = mid + 1
			else:
				if nums[mid] < X:
					count_high_needed += 1
				else:
					count_high_minus += 1
				high = mid - 1
		if count_low_needed == 0 and count_high_needed == 0:
			total = 0
		else:
			total_lows = sorted_index_map[X] - count_low_minus
			total_highs = N - sorted_index_map[X] - 1 - count_high_minus
			if count_low_needed - total_lows > 0 or count_high_needed - total_highs > 0:
				total = -1
			else:
				total = max(count_low_needed, count_high_needed)
		print(total)


def binary(arr, x, check, lowcount, upcount):
	lcount = 0
	ucount = 0
	low = 0
	high = len(arr) - 1
	while low <= high:
		mid = (low + high) // 2
		if arr[mid] == x:
			break
		if low == high and arr[mid] != x:
			break
		elif arr[mid] < x and mid < check:
			if lowcount == 0:
				ucount = -1
				break
			lowcount -= 1
			low = mid + 1
		elif arr[mid] > x and mid > check:
			if upcount == 0:
				lcount = -1
				break
			upcount -= 1
			high = mid - 1
		elif arr[mid] > x and mid < check:
			if lowcount == 0:
				lcount = -1
				break
			else:
				lowcount -= 1
				lcount += 1
				low = mid + 1
		elif arr[mid] < x and mid > check:
			if upcount == 0:
				ucount = -1
				break
			else:
				upcount -= 1
				ucount += 1
				high = mid - 1
		else:
			lcount = -1
			ucount = -1
			break
	return (lcount, ucount)
total = int(input())
for _ in range(total):
	mn = list(map(int, input().split()))
	n = mn[0]
	q = mn[1]
	arr = list(map(int, input().split()))
	arr2 = {}
	arr_sorted = sorted(arr)
	arr2_sorted = {}
	for i in range(len(arr)):
		arr2_sorted[arr_sorted[i]] = i
		arr2[arr[i]] = i
	for _ in range(q):
		x = int(input())
		check = arr2[x]
		check2 = arr2_sorted[x]
		lowcount = check2
		upcount = len(arr2) - check2 - 1
		lowcount2 = lowcount
		upcount2 = upcount
		(lcount, ucount) = binary(arr, x, check, lowcount, upcount)
		if lcount > lowcount2 or ucount > upcount2:
			print(-1)
		elif lcount == -1 or ucount == -1:
			print(-1)
		elif lcount + ucount > 0 and (lowcount == 0 or upcount == 0):
			print(-1)
		else:
			print(max(lcount, ucount))


for t in range(int(input())):
	(N, Q) = [int(x) for x in input().split()]
	A = [int(x) for x in input().split()]
	B = sorted(A)
	D = {}
	for i in range(len(A)):
		D[A[i]] = [i]
	for i in range(len(B)):
		D[B[i]].append(i)
	results = []
	queries = [int(input()) for q in range(Q)]
	for q in queries:
		(low, high) = (1, N)
		index = D[q][0] + 1
		(back, forward) = ([], [])
		maxswap = N - D[q][1] - 1
		minswap = N - maxswap - 1
		stop = 0
		while low <= high:
			mid = (low + high) // 2
			if mid == index:
				break
			elif mid > index:
				high = mid - 1
				if A[mid - 1] < q:
					forward.append(A[mid - 1])
				else:
					maxswap -= 1
			elif mid < index:
				low = mid + 1
				if A[mid - 1] > q:
					back.append(A[mid - 1])
				else:
					minswap -= 1
		(lenf, lenb) = (len(forward), len(back))
		swap = min(lenf, lenb)
		rest = max(lenf, lenb) - swap
		(minswap, maxswap) = (minswap - swap, maxswap - swap)
		swapspace = min(minswap, maxswap)
		if swapspace < rest:
			results.append(-1)
			stop = 1
		elif swapspace >= rest:
			swap += rest
		if not stop:
			results.append(swap)
	for result in results:
		print(result)


from collections import defaultdict
T = int(input())
for t in range(T):
	(n, Q) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	sorted_arr = sorted(arr)
	indexes = defaultdict(list)
	for i in range(n):
		if arr[i] not in indexes:
			indexes[arr[i]] = [-1, -1]
		if sorted_arr[i] not in indexes:
			indexes[sorted_arr[i]] = [-1, -1]
		indexes[arr[i]][0] = i
		indexes[sorted_arr[i]][1] = i
	for q in range(Q):
		x = int(input())
		swaps = 0
		indx = indexes[x][0]
		need_large = 0
		need_small = 0
		safe_large = 0
		safe_small = 0
		low = 0
		high = n - 1
		while low <= high:
			mid = int(low + (high - low) / 2)
			if arr[mid] == x:
				break
			elif arr[mid] < x:
				if indx < mid:
					need_large += 1
					high = mid - 1
				else:
					safe_small += 1
					low = mid + 1
			elif indx > mid:
				need_small += 1
				low = mid + 1
			else:
				safe_large += 1
				high = mid - 1
		swaps += min(need_large, need_small)
		safe_small += swaps
		safe_large += swaps
		if need_large > need_small:
			need = need_large - need_small
			available = n - indexes[x][1] - 1 - safe_large
			if available >= need:
				swaps += need
			else:
				swaps = -1
		elif need_large < need_small:
			need = need_small - need_large
			available = indexes[x][1] - safe_small
			if available >= need:
				swaps += need
			else:
				swaps = -1
		print(swaps)


import copy

def b_search(a, x, b, d_a, d_b, min_swap, max_swap, min_elem, max_elem):
	low = 0
	high = len(a) - 1
	while low <= high:
		mid = (low + high) // 2
		if a[mid] == x:
			break
		elif a[mid] < x:
			if d_a[x] >= mid + 1 and d_a[x] <= high:
				low = mid + 1
				min_elem += 1
			else:
				max_swap += 1
				high = mid - 1
		elif d_a[x] >= low and d_a[x] <= mid - 1:
			high = mid - 1
			max_elem += 1
		else:
			min_swap += 1
			low = mid + 1
	if d_b[x] - min_swap - min_elem >= 0 and d_b[x] + max_swap + max_elem <= len(a) - 1:
		if min_swap >= max_swap:
			return min_swap
		else:
			return max_swap
	else:
		return -1
T = int(input())
for t in range(T):
	[N, Q] = [int(i) for i in input().split(' ')]
	a = [int(j) for j in input().split(' ')]
	b = copy.deepcopy(a)
	b.sort()
	d_b = {}
	for x in range(len(a)):
		d_b[b[x]] = x
	d_a = {}
	for y in range(len(a)):
		d_a[a[y]] = y
	for q in range(Q):
		X = int(input())
		print(b_search(a, X, b, d_a, d_b, 0, 0, 0, 0))


def bySearch(arr, l, r, x):
	if r >= l:
		mid = (l + r) // 2
		if arr[mid][0] == x:
			return int(mid)
		elif arr[mid][0] > x:
			return int(bySearch(arr, l, mid - 1, x))
		else:
			return int(bySearch(arr, mid + 1, r, x))

def merge(arr, l, m, r):
	n1 = m - l + 1
	n2 = r - m
	L = arr[l:m + 1]
	R = arr[m + 1:r + 1]
	i = 0
	j = 0
	k = l
	while i < n1 and j < n2:
		if L[i][0] <= R[j][0]:
			arr[k] = L[i]
			i += 1
		else:
			arr[k] = R[j]
			j += 1
		k += 1
	while i < n1:
		arr[k] = L[i]
		i += 1
		k += 1
	while j < n2:
		arr[k] = R[j]
		j += 1
		k += 1

def mergeSort(arr, l, r):
	if l < r:
		m = (l + r) // 2
		mergeSort(arr, l, m)
		mergeSort(arr, m + 1, r)
		merge(arr, l, m, r)
t = int(input())
for e in range(t):
	(n, q) = [int(x) for x in input().split()]
	a = [[int(x), i] for (i, x) in enumerate(input().split())]
	b = a[:]
	mergeSort(a, 0, n - 1)
	d = {x[0]: i for (i, x) in enumerate(a)}
	for p in range(q):
		x = int(input())
		j = d[x]
		i = a[j][1]
		(l, h, g, s, s1, g1) = (0, n - 1, 0, 0, 0, 0)
		m = h // 2
		while m != i:
			if i > m:
				l = m + 1
				if b[m][0] > x:
					s += 1
				s1 += 1
			else:
				h = m - 1
				if b[m][0] < x:
					g += 1
				g1 += 1
			m = (h + l) // 2
		if s1 <= j and g1 <= n - 1 - j:
			print(max(s, g))
		else:
			print(-1)


import copy
for t in range(int(input())):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	b = copy.deepcopy(a)
	b.sort()
	d = dict()
	d1 = dict()
	for i in range(n):
		d[a[i]] = i
	for i in range(n):
		d1[b[i]] = i
	for que in range(q):
		x = int(input())
		x_a_index = d[x]
		x_b_index = d1[x]
		swaplwr = 0
		swapgrt = 0
		cnth = 0
		cntl = 0
		low = 0
		high = n - 1
		while low <= high:
			mid = (low + high) // 2
			if mid == x_a_index:
				break
			elif mid > x_a_index:
				high = mid - 1
				cnth += 1
				if a[mid] < x:
					swaplwr += 1
			else:
				low = mid + 1
				cntl += 1
				if a[mid] > x:
					swapgrt += 1
		if cntl > x_b_index or cnth > n - (x_b_index + 1):
			print(-1)
		else:
			print(max(swapgrt, swaplwr))


def mergeSort(alist, a):
	b = []
	if len(alist) > 1:
		mid = len(alist) // 2
		lefthalf = alist[:mid]
		righthalf = alist[mid:]
		la = a[:mid]
		ra = a[mid:]
		mergeSort(lefthalf, la)
		mergeSort(righthalf, ra)
		i = 0
		j = 0
		k = 0
		while i < len(lefthalf) and j < len(righthalf):
			if lefthalf[i] < righthalf[j]:
				alist[k] = lefthalf[i]
				a[k] = la[i]
				i = i + 1
			else:
				alist[k] = righthalf[j]
				a[k] = ra[j]
				j = j + 1
			k = k + 1
		while i < len(lefthalf):
			alist[k] = lefthalf[i]
			a[k] = la[i]
			i = i + 1
			k = k + 1
		while j < len(righthalf):
			alist[k] = righthalf[j]
			a[k] = ra[j]
			j = j + 1
			k = k + 1

def index(a, x):
	for i in range(1, len(a) + 1):
		if x == a[i]:
			return i
			break

def cc(a, low, high, x):
	j = 0
	while j < len(a) // 2:
		mid = (low + high) // 2
		if x == a[mid]:
			return mid
			break
		elif x > a[mid]:
			j += 1
			low = mid + 1
		else:
			j += 1
			high = mid - 1

def chalega(a, x, i, si, low, high, b, c, j):
	gx = len(a) - 1 - si
	lx = si - 1
	l = 0
	r = 0
	while j < len(a):
		mid = (low + high) // 2
		if l > lx or r > gx:
			c = -1
			break
		elif i == mid:
			c += 0
			break
		elif i < mid:
			if x > a[mid]:
				r += 1
				high = mid - 1
				j += 1
			elif x < a[mid]:
				gx -= 1
				high = mid - 1
				j += 1
		elif i > mid:
			if x > a[mid]:
				low = mid + 1
				j += 1
				lx -= 1
			else:
				l += 1
				low = mid + 1
				j += 1
	if c != -1:
		if l >= r:
			c = l
		else:
			c = r
	return c
t = int(input())
for i in range(t):
	nq = input().split()
	n = int(nq[0]) + 1
	q = int(nq[1])
	nn = input().split()
	a = [0]
	aa = [0]
	b = [0]
	dic = {}
	for j in range(n - 1):
		dic[int(nn[j])] = j + 1
		a.append(int(nn[j]))
		b.append(int(nn[j]))
	b.sort()
	for k in range(q):
		x = int(input())
		z = cc(b, 1, len(b) - 1, x)
		y = dic[x]
		print(chalega(a, x, y, z, 1, len(a) - 1, b, 0, 0))


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(sorted(a))
	d = {}
	dd = {}
	ddd = {}
	for i in range(n):
		d[a[i]] = i
		dd[b[i]] = i
		ddd[b[i]] = n - i - 1
	for __ in range(q):
		x = int(input())
		pos = d[x]
		left = 0
		right = n - 1
		wg = 0
		wl = 0
		cg = 0
		cl = 0
		while True:
			mid = int((left + right) / 2)
			if mid == pos:
				break
			elif mid > pos:
				if a[mid] < a[pos]:
					wg += 1
				else:
					cg += 1
				right = mid - 1
			elif mid < pos:
				if a[mid] > a[pos]:
					wl += 1
				else:
					cl += 1
				left = mid + 1
		if wl <= dd[x] - cl and wg <= ddd[x] - cg:
			print(max(wl, wg))
		else:
			print('-1')


def createParentArray(a, l, r, root, p):
	if l > r:
		return
	mid = (l + r) // 2
	p[mid] = root
	createParentArray(a, l, mid - 1, mid, p)
	createParentArray(a, mid + 1, r, mid, p)

def getAns(a, p, idx, left, right):
	i = idx
	base = a[idx]
	cnt = 0
	lt_base = 0
	gt_base = 0
	while p[i] != -1:
		if i < p[i]:
			if base > a[p[i]]:
				lt_base += 1
				left -= 1
			else:
				right -= 1
		elif i > p[i]:
			if base < a[p[i]]:
				gt_base += 1
				right -= 1
			else:
				left -= 1
		i = p[i]
	cnt += min(lt_base, gt_base)
	lt_base -= cnt
	gt_base -= cnt
	if lt_base <= right:
		cnt += lt_base
	else:
		return -1
	if gt_base <= left:
		cnt += gt_base
	else:
		return -1
	return cnt

def solve():
	(n, q) = [int(x) for x in input().strip().split()]
	a = [int(x) for x in input().strip().split()]
	p = [0 for x in range(n)]
	createParentArray(a, 0, n - 1, -1, p)
	b = sorted(a)
	h = dict()
	for i in range(n):
		h[a[i]] = i
	for i in range(n):
		h[b[i]] = (h[b[i]], i, n - 1 - i)
	ans = dict()
	for i in range(q):
		x = int(input())
		if x in ans:
			print(ans[x])
			continue
		(idx, left, right) = h[x]
		ans[x] = getAns(a, p, idx, left, right)
		print(ans[x])

def main():
	t = int(input())
	while t > 0:
		solve()
		t -= 1
main()


t = int(input())
for a0 in range(t):
	(n, q) = input().strip().split(' ')
	(n, q) = (int(n), int(q))
	arr1 = list(map(int, input().strip().split(' ')))
	arr = list(arr1)
	arr1.sort()
	ltgt = {}
	ind = {}
	for i in range(len(arr)):
		ind[arr[i]] = i
	for i in range(len(arr1)):
		ltgt[arr1[i]] = [i, n - 1 - i]
	for a1 in range(q):
		x = int(input(''))
		low = 0
		high = n - 1
		smallerreplaced = 0
		largerreplaced = 0
		smallernotreplaced = 0
		largernotreplaced = 0
		while True:
			mid = (low + high) // 2
			if arr[mid] == x:
				break
			elif x < arr[mid] and ind[x] < mid:
				high = mid - 1
				largernotreplaced += 1
			elif x < arr[mid] and ind[x] > mid:
				low = mid + 1
				smallerreplaced += 1
			elif x > arr[mid] and ind[x] > mid:
				low = mid + 1
				smallernotreplaced += 1
			elif x > arr[mid] and ind[x] < mid:
				high = mid - 1
				largerreplaced += 1
		anstillnow = max(largerreplaced, smallerreplaced)
		if largerreplaced + largernotreplaced > ltgt[x][1] or smallerreplaced + smallernotreplaced > ltgt[x][0]:
			ans = -1
		else:
			ans = anstillnow
		print(ans)


from copy import *

def BinarySearch(a, low, high, x, index, minn, maxx, smaller, larger, f):
	low += 1
	minmax = 0
	maxmin = 0
	s = 0
	l = 0
	high += 1
	while high - low >= 0:
		mid = (low + high) // 2
		if mid - index == 0:
			break
		elif mid - index < 0:
			s += 1
			if a[mid - 1] - a[index - 1] < 0:
				if f:
					minmax += 1
			low = mid + 1
		elif mid - index > 0:
			l += 1
			if a[mid - 1] - a[index - 1] > 0:
				if f:
					maxmin += 1
			high = mid - 1
	ans = 0
	if s - smaller <= 0:
		if l - larger <= 0:
			a = s - minmax
			b = l - maxmin
			ans = max(a, b)
			return ans
		else:
			ans = -1
			return ans
	else:
		ans = -1
		return ans
T = int(input())
for t in range(T):
	(N, Q) = map(int, input().split())
	l = list(map(int, input().split()))
	D = {}
	E = {}
	sortedd = sorted(l)
	for i in range(len(l)):
		D[l[i]] = i
	i = 0
	while i < len(l):
		E[sortedd[i]] = i
		i += 1
	minn = sortedd[0]
	maxx = sortedd[-1]
	for q in range(Q):
		x = int(input())
		smaller = E[x]
		larger = len(l) - E[x]
		larger -= 1
		print(BinarySearch(l, 0, len(l) - 1, x, D[x] + 1, minn, maxx, smaller, larger, True))


for i in range(0, int(input())):
	lookUp = {}
	lookUpSorted = {}
	(N, Q) = map(int, input().split())
	A = [int(i) for i in input().split()]
	for (count, i) in enumerate(A):
		lookUp[int(i)] = count
	for (count, i) in enumerate(sorted(A)):
		lookUpSorted[i] = count
	B = [int(input()) for _ in range(Q)]
	for snum in B:
		ll = 0
		ul = len(A) - 1
		smallerSwapable = lookUpSorted[snum]
		largerSwapable = len(A) - (lookUpSorted[snum] + 1)
		incorrectRight = 0
		incorrectLeft = 0
		output = None
		while ul >= ll:
			mid = int((ul + ll) / 2)
			if largerSwapable < 0 or smallerSwapable < 0:
				output = -1
				break
			elif A[mid] == snum:
				break
			elif A[mid] > snum and mid > lookUp[snum]:
				ul = mid - 1
				largerSwapable -= 1
			elif A[mid] > snum and mid < lookUp[snum]:
				ll = mid + 1
				smallerSwapable -= 1
				incorrectLeft += 1
			elif A[mid] < snum and mid < lookUp[snum]:
				ll = mid + 1
				smallerSwapable -= 1
			elif A[mid] < snum and mid > lookUp[snum]:
				ul = mid - 1
				largerSwapable -= 1
				incorrectRight += 1
		if output == None:
			print(abs(incorrectRight - incorrectLeft) + min(incorrectRight, incorrectLeft))
		else:
			print(output)


import collections
T = int(input())
for _ in range(T):
	(N, Q) = [int(i) for i in input().split()]
	list = [int(i) for i in input().split()]
	sorted_list = sorted(list)
	numbers = {}
	sorted_numbers = {}
	j = 0
	for i in list:
		numbers.update({i: j})
		j += 1
	j = 0
	for i in sorted_list:
		sorted_numbers.update({i: j})
		j += 1
	for k in range(Q):
		count1 = 0
		count2 = 0
		more = 0
		less = 0
		X = int(input())
		index = numbers[X]
		found = -1
		a = 0
		b = N - 1
		while True:
			mid = a + (b - a) // 2
			if list[mid] == X:
				break
			elif index > mid and list[mid] > X:
				count1 += 1
				a = mid + 1
				more += 1
			elif index < mid and list[mid] < X:
				count2 += 1
				b = mid - 1
				less += 1
			elif index > mid and list[mid] < X:
				less += 1
				a = mid + 1
			elif index < mid and list[mid] > X:
				more += 1
				b = mid - 1
		index_sort = sorted_numbers[X]
		check = False
		if count2 > count1:
			if count2 - count1 <= N - 1 - index_sort - more:
				check = True
		elif count2 < count1:
			if count1 - count2 <= index_sort - less:
				check = True
		else:
			check = True
		if check:
			print(max([count1, count2]))
		else:
			print('-1')


t = int(input())

def binSearch(data, n, x, pos, avai):
	low = 0
	high = n - 1
	replaceLow = 0
	replaceHigh = 0
	lowUsed = 0
	highUsed = 0
	while low <= high:
		mid = (low + high) // 2
		if mid < pos:
			if data[mid] < x:
				lowUsed += 1
				low = mid + 1
			else:
				replaceLow += 1
				low = mid + 1
		elif mid > pos:
			if data[mid] > x:
				highUsed += 1
				high = mid - 1
			else:
				replaceHigh += 1
				high = mid - 1
		else:
			break
	if replaceHigh + highUsed > n - avai - 1 or replaceLow + lowUsed > avai:
		return -1
	else:
		return min(replaceHigh, replaceLow) + abs(replaceLow - replaceHigh)
for _ in range(t):
	temp = input().split()
	n = int(temp[0])
	q = int(temp[1])
	data = list(map(int, input().split()))
	realPos = {}
	for i in range(0, len(data)):
		realPos[data[i]] = i
	newD = sorted(data)
	posi = {}
	for i in range(0, len(newD)):
		posi[newD[i]] = i
	for __ in range(q):
		ele = int(input())
		print(binSearch(data, n, ele, realPos[ele], posi[ele]))


def inde(x, sarr):
	(low, high) = (1, len(sarr))
	while low <= high:
		mid = (low + high) // 2
		if sarr[mid][1] == x:
			break
		elif sarr[mid][1] < x:
			low = mid + 1
		else:
			high = mid - 1
	return mid

def swapcount(low, high, k, arr, grtmark, lessmark):
	mid = (low + high) // 2
	if mid == k or low > high:
		return [0, 0, grtmark, lessmark]
	elif mid > k and arr[mid] > x:
		return swapcount(low, mid - 1, k, arr, grtmark + 1, lessmark)
	elif mid > k and arr[mid] < x:
		temp = swapcount(low, mid - 1, k, arr, grtmark, lessmark)
		return [temp[0], temp[1] + 1, temp[2], temp[3]]
	elif mid < k and arr[mid] < x:
		return swapcount(mid + 1, high, k, arr, grtmark, lessmark + 1)
	elif mid < k and arr[mid] > x:
		temp = swapcount(mid + 1, high, k, arr, grtmark, lessmark)
		return [temp[0] + 1, temp[1], temp[2], temp[3]]
t = int(input())
while t:
	t -= 1
	arr = [0]
	sarr = list()
	(n, q) = [int(nag) for nag in input().split()]
	sat = [int(satish) for satish in input().split()]
	arr += sat
	for i2 in range(0, n + 1):
		ltem = [i2, arr[i2]]
		sarr.append(ltem)
	sarr.sort(key=lambda x: x[1])
	while q:
		q -= 1
		x = int(input())
		pos = inde(x, sarr)
		k = sarr[pos][0]
		ans = swapcount(1, n, k, arr, 0, 0)
		uless = pos - 1 - ans[3]
		uhigh = n - pos - ans[2]
		if uless >= ans[0] and uhigh >= ans[1]:
			print(max(ans[0], ans[1]))
		else:
			print('-1')


def Bin(arr, lo, hi, x):
	res = False
	while lo <= hi:
		mid = (lo + hi) // 2
		if arr[mid] == x:
			res = True
			break
		elif arr[mid] < x:
			lo = mid + 1
		else:
			hi = mid - 1
	return res

def Function(arr, new, dict, low, high, x):
	count = 0
	count_1 = 0
	count_2 = 0
	count_3 = 0
	count_4 = 0
	while low < high:
		mid = (low + high) // 2
		if arr[mid] > x and mid < new[x]:
			low = mid + 1
			count_1 += 1
		elif arr[mid] < x and mid > new[x]:
			high = mid - 1
			count_2 += 1
		elif arr[mid] > x and mid > new[x]:
			high = mid - 1
			count_4 += 1
		elif arr[mid] < x and mid < new[x]:
			low = mid + 1
			count_3 += 1
		else:
			break
	ans = max(count_1, count_2)
	if count_1 > dict[x] - count_3 or count_2 > n - dict[x] - 1 - count_4:
		ans = -1
	return ans
t = int(input())
for i1 in range(t):
	(n, q) = map(int, input().split())
	arr = list(map(int, input().split()))
	new = {}
	t1 = 0
	for i in arr:
		new[i] = t1
		t1 += 1
	dict = {}
	index = 0
	y = arr[:]
	y = sorted(y)
	for i in y:
		dict[i] = index
		index += 1
	for i in range(q):
		x = int(input())
		r1 = Bin(y, 0, n - 1, x)
		r2 = Bin(arr, 0, n - 1, x)
		if r1 == r2:
			print('0')
		elif r1 == True and r2 == False:
			print(Function(arr, new, dict, 0, n - 1, x))


T = int(input())
for t in range(T):
	(N, Q) = map(int, input().split())
	if N > 10:
		L1 = list(map(int, input().split()))
		L1.insert(0, -1)
		L2 = L1[:]
		L2.sort()
		D2 = dict()
		for i in range(1, N + 1):
			D2[L2[i]] = i
		D = dict()
		for i in range(1, N + 1):
			D[L1[i]] = i
		for q in range(Q):
			ctr = 0
			A = int(input())
			K = D[A]
			low = 1
			high = N
			flag = True
			lr = 0
			ld = 0
			sr = 0
			sd = 0
			while low <= high:
				mid = (high + low) // 2
				if L1[mid] == A:
					flag = False
					break
				elif L1[mid] > A and K > mid:
					ld += 1
					sr += 1
					low = mid + 1
				elif L1[mid] > A and K < mid:
					ld += 1
					high = mid - 1
				elif L1[mid] < A and K > mid:
					sd += 1
					low = mid + 1
				elif L1[mid] < A and K < mid:
					sd += 1
					lr += 1
					high = mid - 1
			if flag == True or ld + lr > N - D2[A] or sd + sr >= D2[A]:
				print(-1)
			elif lr == sr:
				print(sr)
			else:
				print(max(sr, lr))
	else:
		L1 = list(map(int, input().split()))
		L1.insert(0, -1)
		L2 = []
		for i in L1:
			L2.append(i)
		L2.sort()
		D2 = dict()
		for i in range(1, N + 1):
			D2[L2[i]] = i
		D = dict()
		for i in range(1, N + 1):
			D[L1[i]] = i
		for q in range(Q):
			ctr = 0
			A = int(input())
			K = D[A]
			low = 1
			high = N
			flag = True
			lctr = 0
			rctr = 0
			lctr2 = 0
			rctr2 = 0
			while low <= high:
				mid = (high + low) // 2
				if L1[mid] == A:
					flag = False
					break
				elif L1[mid] > A and K > mid:
					ctr += 1
					rctr += 1
					rctr2 += 1
					low = mid + 1
				elif L1[mid] > A and K < mid:
					lctr += 1
					high = mid - 1
				elif L1[mid] < A and K > mid:
					low = mid + 1
					rctr += 1
				elif L1[mid] < A and K < mid:
					ctr += 1
					lctr2 += 1
					high = mid - 1
					lctr += 1
			if flag == True or lctr > N - D2[A] or rctr >= D2[A]:
				print(-1)
			elif lctr2 == rctr2:
				print(lctr2)
			else:
				print(abs(lctr2 - rctr2))


def bsearch(arr, size, ind):
	mid = 0
	left = 0
	right = size - 1
	reqToGrt = 0
	reqToLess = 0
	changeToGrt = 0
	changeToLess = 0
	while left <= right:
		mid = (left + right) // 2
		if ind == mid:
			break
		if ind < mid:
			if arr[ind] > arr[mid]:
				changeToGrt += 1
			reqToGrt += 1
			right = mid - 1
		else:
			if arr[ind] < arr[mid]:
				changeToLess += 1
			reqToLess += 1
			left = mid + 1
	return (reqToGrt, reqToLess, changeToGrt, changeToLess)

def main():
	t = int(input())
	for _ in range(t):
		(n, q) = tuple(map(int, input().split()))
		pos = {}
		rank = {}
		arr = list(map(int, input().split()))
		b = sorted(arr)
		for i in range(n):
			pos[arr[i]] = i
			rank[b[i]] = i
		for i in range(q):
			x = int(input())
			cnt_less = rank[x]
			cnt_grt = n - rank[x] - 1
			(reqToGrt, reqToLess, changeToGrt, changeToLess) = bsearch(arr, n, pos[x])
			if reqToGrt > cnt_grt or reqToLess > cnt_less:
				ans = -1
			else:
				ans = min(changeToLess, changeToGrt) + abs(changeToGrt - changeToLess)
			print(ans)
main()


def fake_bs(inputs, n, dest_idx, elements_before_q, elements_after_q, res):
	if dest_idx in res:
		return res[dest_idx]
	l = 0
	h = n - 1
	before_swaps = 0
	after_swaps = 0
	while l <= h:
		mid = (l + h) // 2
		if mid == dest_idx:
			res[dest_idx] = max(before_swaps, after_swaps)
			break
		elif dest_idx > mid and elements_before_q > 0:
			if inputs[mid] > inputs[dest_idx]:
				before_swaps += 1
			elements_before_q -= 1
			l = mid + 1
		elif dest_idx < mid and elements_after_q > 0:
			if inputs[mid] < inputs[dest_idx]:
				after_swaps += 1
			elements_after_q -= 1
			h = mid - 1
		else:
			res[dest_idx] = -1
			break
	return res[dest_idx]
t = int(input())
while t:
	t -= 1
	inputs = list(map(int, input().split()))
	(n, q) = (inputs[0], inputs[1])
	inputs = list(map(int, input().split()))
	res = {}
	is_sorted = True
	index_of = {}
	for i in range(n):
		index_of[inputs[i]] = i
		if is_sorted and i > 0 and (inputs[i - 1] > inputs[i]):
			is_sorted = False
	sorted_index_of = {}
	if not is_sorted:
		sorted_inputs = sorted(inputs)
		for i in range(n):
			sorted_index_of[sorted_inputs[i]] = i
	for i in range(q):
		num = int(input())
		if is_sorted:
			print(0)
			continue
		print(fake_bs(inputs, n, index_of[num], sorted_index_of[num], n - 1 - sorted_index_of[num], res))


from collections import defaultdict
T = int(input())
for t in range(T):
	(n, Q) = list(map(int, input().split()))
	arr = list(map(int, input().split()))
	if n <= 1000:
		for q in range(Q):
			x = int(input())
			swaps = 0
			indx = arr.index(x)
			need_large = set()
			need_small = set()
			safe = set()
			low = 0
			high = n - 1
			while low <= high:
				mid = int(low + (high - low) / 2)
				if arr[mid] == x:
					safe.add(mid)
					break
				elif arr[mid] < x:
					if indx < mid:
						need_large.add(mid)
						high = mid - 1
					else:
						safe.add(mid)
						low = mid + 1
				elif indx > mid:
					need_small.add(mid)
					low = mid + 1
				else:
					safe.add(mid)
					high = mid - 1
			while len(need_small) != 0 and len(need_large) != 0:
				safe.add(need_small.pop())
				safe.add(need_large.pop())
				swaps += 1
			else:
				if len(need_small) == 0 and len(need_large) == 0:
					print(swaps)
					continue
			large_available = set()
			small_available = set()
			for i in range(n):
				if i not in safe:
					if arr[i] < x:
						if len(need_small) != 0:
							need_small.pop()
							swaps += 1
						elif len(need_large) == 0:
							break
					elif len(need_large) != 0:
						need_large.pop()
						swaps += 1
					elif len(need_small) == 0:
						break
			if len(need_small) == 0 and len(need_large) == 0:
				print(swaps)
			else:
				print(-1)
	else:
		sorted_arr = sorted(arr)
		indexes = defaultdict(list)
		for i in range(n):
			if arr[i] not in indexes:
				indexes[arr[i]] = [-1, -1]
			if sorted_arr[i] not in indexes:
				indexes[sorted_arr[i]] = [-1, -1]
			indexes[arr[i]][0] = i
			indexes[sorted_arr[i]][1] = i
		for q in range(Q):
			x = int(input())
			swaps = 0
			indx = indexes[x][0]
			need_large = 0
			need_small = 0
			safe_large = 0
			safe_small = 0
			low = 0
			high = n - 1
			while low <= high:
				mid = int(low + (high - low) / 2)
				if arr[mid] == x:
					break
				elif arr[mid] < x:
					if indx < mid:
						need_large += 1
						high = mid - 1
					else:
						safe_small += 1
						low = mid + 1
				elif indx > mid:
					need_small += 1
					low = mid + 1
				else:
					safe_large += 1
					high = mid - 1
			swaps += min(need_large, need_small)
			if need_large > need_small:
				need = need_large - need_small
				available = n - indexes[x][1] - 1 - safe_large
				if available >= need:
					swaps += need
				else:
					swaps = -1
			elif need_large < need_small:
				need = need_small - need_large
				available = indexes[x][1] - safe_small
				if available >= need:
					swaps += need
				else:
					swaps = -1
			print(swaps)


import math

def binary_search(index, X, N, A, sortedA):
	(lo, hi) = (1, N)
	sortedIndex = -1
	while lo <= hi:
		mid = int((lo + hi) / 2)
		if sortedA[mid] == X:
			sortedIndex = mid
			break
		elif sortedA[mid] > X:
			hi = mid - 1
		else:
			lo = mid + 1
	(lo, hi) = (1, N)
	(lessThanXAvailableCount, largerThanXAvailableCount) = (sortedIndex - 1, N - sortedIndex)
	(lessThanXRequiredCount, largerThanXRequiredCount) = (0, 0)
	while lo <= hi:
		mid = int((lo + hi) / 2)
		if mid == index:
			break
		elif mid < index:
			if A[mid] < X:
				lessThanXAvailableCount -= 1
			elif A[mid] > X:
				lessThanXRequiredCount += 1
			else:
				print('CRAP')
			lo = mid + 1
		else:
			if A[mid] > X:
				largerThanXAvailableCount -= 1
			elif A[mid] < X:
				largerThanXRequiredCount += 1
			else:
				print('CRAP')
			hi = mid - 1
	if lessThanXRequiredCount <= lessThanXAvailableCount and largerThanXRequiredCount <= largerThanXAvailableCount:
		return min(lessThanXRequiredCount, largerThanXRequiredCount) + (lessThanXRequiredCount - min(lessThanXRequiredCount, largerThanXRequiredCount)) + (largerThanXRequiredCount - min(lessThanXRequiredCount, largerThanXRequiredCount))
	else:
		return -1
T = int(input())
for t in range(T):
	(N, Q) = list(map(int, input().split()))
	A = [0] + list(map(int, input().split()))
	invA = dict()
	for i in range(1, N + 1):
		invA[A[i]] = i
	sortedA = sorted(A)
	for q in range(Q):
		sol = -1
		X = int(input())
		index = -1
		if X in invA:
			index = invA[X]
		if index >= 1 and index <= N:
			sol = binary_search(index, X, N, A, sortedA)
		print(sol)


t = int(input())
for a0 in range(t):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	dicta = {}
	for i in range(n):
		dicta[a[i]] = i
	c = []
	b = []
	for i in range(n):
		b.append(i)
	d = []
	for i in a:
		d.append(i)
	d.sort()
	dictd = {}
	for i in range(n):
		dictd[d[i]] = i
	for i in range(q):
		num = int(input())
		pos = dicta[num]
		c = []
		low = 0
		high = n - 1
		while low <= high:
			mid = (low + high) // 2
			c.append(b[mid])
			if b[mid] == pos:
				break
			elif b[mid] < pos:
				low = mid + 1
			else:
				high = mid - 1
		ct1 = ct2 = ct3 = ct4 = 0
		for i in range(len(c) - 1):
			if c[i] < c[i + 1]:
				if a[c[i]] > num:
					ct1 += 1
				ct3 += 1
			else:
				if a[c[i]] < num:
					ct2 += 1
				ct4 += 1
		if ct3 <= dictd[num] and ct4 <= n - dictd[num] - 1:
			print(max(ct1, ct2))
		else:
			print(-1)


from collections import defaultdict
t = int(input())
for z in range(t):
	(n, q) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	fg = sorted(a)
	b = {a[i]: i for i in range(len(a))}
	bs = {fg[i]: i for i in range(len(a))}
	b = defaultdict(int, b)
	bs = defaultdict(int, bs)
	debug = False
	if debug:
		print(b)
		print(bs)
	for zy in range(q):
		x = int(input())
		xidx = b[x]
		xsidx = bs[x]
		ch = len(a) - xsidx - 1
		cl = xsidx
		low = 0
		high = len(a) - 1
		swaps = 0
		cls = 0
		chs = 0
		if debug:
			print(xidx, xsidx)
		while low <= high:
			mid = (low + high) // 2
			if a[mid] == x:
				break
			elif mid < xidx:
				cl -= 1
				if a[mid] > x:
					cls += 1
					swaps += 1
				low = mid + 1
			else:
				ch -= 1
				if a[mid] < x:
					chs += 1
					swaps += 1
				high = mid - 1
			if debug:
				print('mid:', mid, 'low:', low, 'high:', high, 'swaps:', swaps)
				print('ch', ch, 'cl', cl)
		swaps = max(cls, chs)
		if ch < 0 or cl < 0:
			swaps = -1
		print(swaps)


t = int(input())
for _ in range(t):
	(n, q) = map(int, input().split())
	ls = list(map(int, input().split()))
	d = {}
	for i in range(n):
		d[ls[i]] = i
	sl = sorted(ls)
	ds = {}
	for i in range(n):
		ds[sl[i]] = i
	for __ in range(q):
		x = int(input())
		ind = d[x]
		h = n - 1
		l = 0
		il = []
		while h >= l:
			m = h + l >> 1
			il.append(m)
			if m == ind:
				break
			elif m < ind:
				l = m + 1
			else:
				h = m - 1
		g = 0
		l = 0
		G = 0
		L = 0
		for i in range(len(il) - 1):
			if il[i] > il[i + 1] and ls[il[i]] < x:
				g += 1
			elif il[i] > il[i + 1]:
				G += 1
			elif il[i] < il[i + 1] and ls[il[i]] > x:
				l += 1
			elif il[i] < il[i + 1]:
				L += 1
		ix = ds[x]
		if ix >= l + L and n - ix - 1 >= g + G:
			print(max(l, g))
		else:
			print(-1)


def main():
	t = int(input())
	for _ in range(t):
		(n, q) = map(int, input().split())
		a = list(map(int, input().split()))
		A = [*a]
		mapp = dict()
		for i in range(n):
			mapp[a[i]] = [i]
		a.sort()
		for i in range(n):
			mapp[a[i]].append(i)
			mapp[a[i]].append(n - i - 1)
		for _ in range(q):
			x = int(input())
			(mid, ans, low, high, Xi, g, l, L, G) = (0, 0, 0, n - 1, mapp[x][0], 0, 0, mapp[x][1], mapp[x][2])
			while low <= high:
				mid = low + (high - low) // 2
				if Xi < mid:
					if A[mid] < x:
						if G > 0:
							g += 1
							G -= 1
						else:
							ans = -1
							break
					else:
						G -= 1
						if G < 0:
							ans = -1
							break
					high = mid - 1
				elif Xi > mid:
					if A[mid] > x:
						if L > 0:
							l += 1
							L -= 1
						else:
							ans = -1
							break
					else:
						L -= 1
						if L < 0:
							ans = -1
							break
					low = mid + 1
				else:
					break
			if ans == -1:
				print(-1)
			else:
				print(g if g > l else l)
main()


def binary_search(a, n, x, d, ls):
	low = 0
	high = n - 1
	l = ls[x]
	h = ls[x]
	li = 0
	lh = 0
	while low <= high:
		mid = (low + high) // 2
		if a[mid] == x:
			break
		elif a[mid] < x:
			if d[x] < mid:
				high = mid - 1
				h = h + 1
				lh = lh + 1
			else:
				low = mid + 1
				l = l - 1
		elif d[x] > mid:
			low = mid + 1
			l = l - 1
			li = li + 1
		else:
			high = mid - 1
			h = h + 1
	if h > n - 1 or l < 0:
		return -1
	return max(li, lh)
T = int(input())
for t in range(T):
	(n, q) = map(int, input().split())
	l = list(map(int, input().split()))
	d = {}
	for i in range(n):
		d[l[i]] = i
	k = sorted(l)
	ls = {}
	for i in range(n):
		ls[k[i]] = i
	for i in range(q):
		x = int(input())
		s = binary_search(l, n, x, d, ls)
		print(s)


t = int(input().strip())

def binary_search(a, val):
	index = dic[val]
	n_lo_val = dic2[val]
	n_high_val = n - 1 - dic2[val]
	mutual_swap1 = []
	mutual_swap2 = []

	def checktruepath(n_lo_val, n_high_val):
		low1 = 0
		high1 = n - 1
		while low1 <= high1:
			mid = (low1 + high1) // 2
			if a[mid] == val:
				break
			elif a[mid] < val:
				if index > mid:
					n_lo_val -= 1
					low1 = mid + 1
				else:
					mutual_swap1.append(a[mid])
					high1 = mid - 1
			elif index < mid:
				n_high_val -= 1
				high1 = mid - 1
			else:
				mutual_swap2.append(a[mid])
				low1 = mid + 1
		return (n_lo_val, n_high_val)
	(n_lo_val, n_high_val) = checktruepath(n_lo_val, n_high_val)
	low = 0
	high = n - 1
	swaps = 0
	while low <= high:
		mid = (low + high) // 2
		if a[mid] == val:
			break
		elif a[mid] < val:
			if index > mid:
				low = mid + 1
			elif n_high_val:
				swaps += 1
				n_high_val -= 1
				high = mid - 1
			else:
				swaps = -1
				break
		elif index < mid:
			high = mid - 1
		elif n_lo_val:
			swaps += 1
			n_lo_val -= 1
			low = mid + 1
		else:
			swaps = -1
			break
	if swaps == -1:
		return swaps
	else:
		return swaps - min(len(mutual_swap2), len(mutual_swap1))
for i in range(t):
	(n, q) = [int(i) for i in input().strip().split(' ')]
	lis1 = [int(i) for i in input().strip().split(' ')]
	dic = {}
	for i in range(n):
		dic[lis1[i]] = i
	lis2 = []
	for i in lis1:
		lis2.append(i)
	dic2 = {}
	lis2.sort()
	for i in range(n):
		dic2[lis2[i]] = i
	for i in range(q):
		quer = int(input())
		swaps = binary_search(lis1, quer)
		print(swaps)