Given two arrays a and b. Given q queries each having a positive integer i denoting an index of the array a. For each query, your task is to find all the elements less than or equal to q_{i} in the array b.
Example 1:
Input:
N=6
a[] = {1, 2, 3, 4, 7, 9}
b[] = {0, 1, 2, 1, 1, 4} 
Query 1 -> 5
Query 2 -> 4
Output : 6
         6
Explanation: For 1^{st} query, the given index is 5,
             A[5] is 9 and in B all the elements 
             are smaller than 9.
             For 2^{nd} query, the given index is 4, 
             A[4] is 7 and in B all the elements 
             are smaller than 7.   
Your Task:
Since, this is a function problem. You don't need to take any input, as it is already accomplished by the driver code. You just need to complete the function find() that takes array a , array b, array q as parameters and returns an array that contains the answer to the corresponding queries. 
 
Expected Time Complexity: O(n).
Expected Auxiliary Space: O(n).
 
Constraints:
1 ≤ n ≤ 10^{7}

Source: geeksforgeeks | Difficulty: EASY
Tags: String algorithms

Data structures

Starter code: #User function Template for python3



def find(a,b,q):

    

Solutions:
def find(a, b, q):
	cnt = []
	for i in q:
		cnt1 = 0
		for j in range(n):
			if a[i] >= b[j]:
				cnt1 += 1
		cnt.append(cnt1)
	return cnt


def find(a, b, q):
	l = []
	for i in q:
		value = a[i]
		c = 0
		for j in b:
			if j <= value:
				c += 1
		l.append(c)
	return l


def find(a, b, q):
	j = 0
	result = []
	while j < len(q):
		ele = a[q[j]]
		count = 0
		for i in range(len(b)):
			if b[i] <= ele:
				count += 1
		result.append(count)
		j += 1
	return result


def find(a, b, q):
	list1 = []
	for i in range(0, len(q)):
		ind = q[i]
		val = a[ind]
		c = 0
		for j in range(0, len(b)):
			if b[j] <= val:
				c = c + 1
		list1.append(c)
	return list1


def find(a, b, q):
	arr = []
	for e in q:
		val = a[e]
		count = 0
		for e2 in b:
			if e2 <= val:
				count += 1
		arr.append(count)
	return arr


import collections

def find(a, b, q):
	dict1 = collections.Counter(b)
	counts = []
	for k in q:
		p = a[k]
		totalcount = 0
		for j in dict1:
			if j <= p:
				totalcount += dict1[j]
		counts.append(totalcount)
	return counts


def find(a, b, q):
	c = []
	for i in q:
		d = 0
		A = a[i]
		for j in b:
			if j <= A:
				d += 1
		c.append(d)
	return c


def find(a, b, q):
	d = {a[i]: 0 for i in q}
	for i in d:
		for j in b:
			if i >= j:
				d[i] += 1
	l = [d[a[i]] for i in q]
	return l


def count_result(b, number):
	count = 0
	for i in b:
		if i <= number:
			count += 1
	return count

def find(a, b, q):
	range_arr = []
	for i in q:
		range_arr.append(a[i])
	res = []
	for i in range(len(range_arr)):
		counter = count_result(b, range_arr[i])
		res.append(counter)
	return res


def find(a, b, q):
	p = a.copy()
	c = sorted(b)
	l = []
	d = {}
	p.sort(reverse=True)
	i = len(p) - 1
	j = 0
	if p[0] < c[0]:
		return [0] * len(q)
	while i >= 0 and j < len(p):
		if p[j] >= c[i]:
			if p[j] not in d:
				d[p[j]] = i
			j += 1
		else:
			i -= 1
	for i in p:
		if i not in d:
			d[i] = -1
	for i in q:
		l.append(d[a[i]] + 1)
	return l


def find(a, b, q):
	res = []
	for i in q:
		element = a[i]
		count = 0
		for i in b:
			if i <= element:
				count += 1
		res.append(count)
	return res


def find(a, b, q):
	ans = []
	for ele in q:
		curr_ele = a[ele]
		count = 0
		for i in range(len(b)):
			if b[i] <= curr_ele:
				count += 1
		ans.append(count)
	return ans


from collections import Counter

def find(a, b, q) -> int:
	result = []
	bc = Counter(b)
	for qe in q:
		leq = 0
		for (k, v) in bc.items():
			if k <= a[qe]:
				leq += v
		result.append(leq)
	return result


def find(a, b, q) -> int:
	result = []
	for qe in q:
		leq = 0
		for be in b:
			if be <= a[qe]:
				leq += 1
		result.append(leq)
	return result


def find(a, b, q):
	res = []
	for i in q:
		s = a[i]
		c = 0
		for i in b:
			if i <= s:
				c += 1
		res.append(c)
	return res


from collections import Counter

def find(a, b, q):
	t = Counter(b)
	c = 0
	u = []
	for i in range(len(q)):
		x = a[q[i]]
		for j in t:
			if j <= x:
				c = c + t[j]
		u.append(c)
		c = 0
	return u


def find(a, b, q):
	res = []
	b.sort()
	for i in q:
		num = a[i]
		if b[0] > num:
			res.append(0)
		elif b[-1] <= num:
			res.append(len(b))
		else:
			upper_bound = binary(b, num)
			res.append(upper_bound)
	return res

def binary(arr, target):
	return binaryHelper(arr, target, 0, len(arr) - 1)

def binaryHelper(arr, t, left, right):
	if right == left + 1:
		return right
	mid = (left + right) // 2
	if arr[mid] <= t and arr[mid + 1] > t:
		return mid + 1
	elif arr[mid] <= t:
		return binaryHelper(arr, t, mid + 1, right)
	elif arr[mid] > t and arr[mid - 1] <= t:
		return mid
	else:
		return binaryHelper(arr, t, left, mid - 1)


def find(a, b, q):
	temp = []
	for i in range(len(q)):
		temp.append(a[q[i]])
	cout = 0
	res = []
	while temp:
		s = temp.pop(0)
		for i in b:
			if i <= s:
				cout += 1
		res.append(cout)
		cout = 0
	return res


def find(a, b, q):
	ans = list()
	for i in range(len(q)):
		indx = q[i]
		num = a[indx]
		count = j = 0
		while j < len(b):
			if b[j] <= num:
				count += 1
			j += 1
		ans.append(count)
	return ans


def find(a, b, q):
	hosa = []
	for i in q:
		new = a[i]
		c = 0
		for i in b:
			if i <= new:
				c += 1
		hosa.append(c)
	return hosa


def find(a, b, q):
	l = []
	for i in q:
		l.append(a[i])
	c = 0
	l1 = []
	while l:
		a = l.pop(0)
		for i in b:
			if i <= a:
				c += 1
		l1.append(c)
		c = 0
	return l1


def find(a, b, q):
	r = []
	for i in q:
		s = a[i]
		count = 0
		for i in b:
			if s >= i:
				count += 1
		r.append(count)
	return r


from collections import Counter

def find(a, b, q):
	c = Counter(b)
	result = []
	for query in q:
		summa = 0
		for item in sorted(c):
			if a[query] < item:
				break
			summa += c[item]
		result.append(summa)
	return result


def find(a, b, q):
	res = []
	import bisect
	b.sort()
	n = len(b)
	for i in q:
		val = a[i]
		ind = bisect.bisect_right(b, val)
		res.append(ind)
	return res


def find(a, b, q):
	b.sort()
	ans = []
	for i in q:
		count = 0
		c = a[i]
		for j in b:
			if j <= c:
				count += 1
		ans.append(count)
	return ans


def find(a, b, q):
	b.sort()
	li = []
	for i in range(len(q)):
		x = a[q[i]]
		count = 0
		for j in range(len(b)):
			if x >= b[j]:
				count += 1
		li.append(count)
	return li


def find(a, b, q):
	ans = []
	for i in range(len(q)):
		c = 0
		s = a[q[i]]
		for j in range(len(b)):
			if b[j] <= s:
				c += 1
		ans.append(c)
	return ans


from bisect import bisect_left

def find(a, b, q):
	b.sort()
	result = []

	def elementLessThanEqual(b, key):
		i = bisect_left(b, key + 1)
		return len(b[:i])
	for index in q:
		key = a[index]
		result.append(elementLessThanEqual(b, key))
	return result


def find(a: list, b: list, q: list) -> list:
	counts = []
	for i in q:
		number = a[i]
		count = 0
		for x in b:
			if x <= number:
				count += 1
		counts.append(count)
	return counts


def find(a, b, q):
	maxele = max(max(a), max(b))
	hm = {}
	for i in range(0, maxele + 1):
		hm[i] = 0
	for ele in b:
		hm[ele] += 1
	for ele in range(1, maxele + 1):
		hm[ele] += hm[ele - 1]
	ans = []
	for idx in q:
		ele = a[idx]
		ans.append(hm[ele])
	return ans


def find(a, b, q):
	indices = {}
	for i in range(len(a)):
		indices[i] = a[i]
	a.sort()
	b.sort()
	(i, j) = (0, 0)
	smaller = {}
	for ele in a:
		smaller[ele] = 0
	prev = a[0]
	while i < len(a):
		ele = a[i]
		while j < len(b) and b[j] <= a[i]:
			smaller[ele] = 1 + smaller.get(ele, 0)
			j += 1
		if ele == prev:
			i += 1
			continue
		else:
			smaller[ele] += smaller[prev]
		prev = ele
		i += 1
	ans = []
	for idx in q:
		ele = indices[idx]
		ans.append(smaller[ele])
	return ans


def find(a, b, q):
	c = 0
	l = []
	for i in range(len(q)):
		k = a[q[i]]
		for j in range(len(b)):
			if b[j] <= k:
				c += 1
		l.append(c)
		c = 0
	return l


def find(a, b, q):
	ar = []
	for i in q:
		a1 = a[i]
		c = 0
		for j in b:
			if j <= a1:
				c += 1
		ar.append(c)
	return ar


def findCount(b, elm):
	cnt = 0
	for i in b:
		if i <= elm:
			cnt += 1
	return cnt

def find(a, b, q):
	res = []
	for i in q:
		search_elm = a[i]
		res.append(findCount(b, search_elm))
	return res


def find(a, b, q):
	ans = []
	for i in q:
		search_ele = a[i]
		c = 0
		for i in b:
			if i <= search_ele:
				c += 1
		ans.append(c)
	return ans


def find(a, b, q):
	m = {}
	for i in b:
		if i in m:
			m[i] += 1
		else:
			m[i] = 1
	d = []
	for i in range(max(a) + 1):
		c = 0
		for j in m:
			if i >= j:
				c += m[j]
		d.append(c)
	ans = []
	for i in q:
		ans.append(d[a[i]])
	return ans


def find(a, b, q):
	ans = []
	for j in q:
		index = a[j]
		res = 0
		for i in range(len(b)):
			if b[i] <= index:
				res += 1
		ans.append(res)
	return ans


def find(a, b, q):
	res = []
	for j in q:
		search_elm = a[j]
		cnt = 0
		for i in b:
			if i <= search_elm:
				cnt += 1
		res.append(cnt)
	return res


def search(arr, target):
	count = 0
	for i in range(n):
		if arr[i] <= target:
			count += 1
		else:
			break
	return count

def find(a, b, q):
	b.sort()
	ans = []
	for i in q:
		target = a[i]
		ans.append(search(b, target))
	return ans


def find(a, b, q):
	ans = []
	for i in q:
		ele = a[i]
		count = 0
		for i in b:
			if i <= ele:
				count += 1
		ans.append(count)
	return ans


def find(a, b, q):
	r = []
	for i in q:
		k = a[i]
		m = 0
		for j in b:
			if k >= j:
				m = m + 1
		r.append(m)
	return r


def find(a, b, q):
	from bisect import bisect_right
	temp = sorted(b)
	ans = []
	for ind in q:
		number = a[ind]
		ans.append(bisect_right(temp, number))
	return ans


def find(a, b, q):
	b.sort()
	c = []
	for i in range(len(q)):
		p = a[q[i]]
		b.append(p)
		b.sort()
		l = b.index(p) + b.count(p) - 1
		c.append(l)
		b.remove(p)
	return c
t = int(input())
for _ in range(0, t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	qsz = int(input())
	q = []
	for i in range(0, qsz):
		q.append(int(input()))
	ans = find(a, b, q)
	for i in range(0, qsz):
		print(ans[i])


def find(a, b, q):
	ans = []
	for i in q:
		k = a[i]
		counter = 0
		for j in b:
			if j <= k:
				counter = counter + 1
		ans.append(counter)
	return ans


def find(a, b, q):
	res = []
	for i in q:
		temp = []
		for j in range(len(b)):
			if b[j] <= a[i]:
				temp.append(b[j])
		res.append(len(temp))
	return res


def find(a, b, q):
	res = []
	b.sort()
	for i in q:
		ele = a[i]
		count = 0
		for j in b:
			if j <= ele:
				count += 1
			else:
				break
		res.append(count)
	return res


def find(a, b, q):
	frecuency = dict()
	sol = []
	for value in b:
		if value not in frecuency:
			frecuency[value] = 0
		frecuency[value] = frecuency[value] + 1
	prevVal = 0
	if prevVal not in frecuency:
		frecuency[prevVal] = 0
	for number in range(1, max(a) + 1):
		if number not in frecuency:
			frecuency[number] = 0
		frecuency[number] = frecuency[number] + frecuency[prevVal]
		prevVal = number
	for query in q:
		sol.append(frecuency[a[query]])
	return sol


def find(a, b, q):
	res = []
	for i in q:
		ele = a[i]
		cnt = 0
		for i in b:
			if i <= ele:
				cnt += 1
		res.append(cnt)
	return res


def find(a, b, q):
	d = []
	for i in range(len(q)):
		x = a[q[i]]
		c = 0
		for i in range(len(b)):
			if b[i] <= x:
				c += 1
		d.append(c)
	return d


import heapq

def find(a, b, query):
	size = len(b)
	b.sort()
	ans = []
	for q in query:
		temp = False
		for j in range(size - 1, -1, -1):
			if a[q] >= b[j]:
				ans.append(j + 1)
				temp = True
				break
		if temp == False:
			ans.append(0)
	return ans


def find(a, b, q):
	n = len(a)
	max = -1
	for i in range(0, n):
		if a[i] > max:
			max = a[i]
	h = [0] * 10 ** 7
	for i in range(0, n):
		h[b[i]] += 1
	for i in range(1, max + 1):
		h[i] += h[i - 1]
	ans = []
	for i in range(0, len(q)):
		ans.append(h[a[q[i]]])
	return ans


def find(a, b, q):
	cnt = 0
	res = []
	for val in q:
		cnt = 0
		for x in b:
			if x <= a[val]:
				cnt += 1
		res.append(cnt)
	return res


def find(a, b, q):
	res = []
	for x in q:
		m = a[x]
		ct = 0
		for x in b:
			if x <= m:
				ct += 1
		res.append(ct)
	return res


def find(a, b, q):

	def findcnt(b, val):
		cnt = 0
		for i in b:
			if i <= val:
				cnt += 1
		return cnt
	res = []
	for i in q:
		val = a[i]
		res.append(findcnt(b, val))
	return res


def f1(b, ptr1):
	count = 0
	for j in range(len(b)):
		if b[j] <= ptr1:
			count = count + 1
	return count

def find(a, b, q):
	list1 = []
	for i in range(len(q)):
		ptr = q[i]
		ans = f1(b, a[ptr])
		list1.append(ans)
	return list1


def find(a, b, q):
	res = [0 for _ in range(len(q))]
	b.sort()
	for i in range(len(q)):
		cnt = 0
		for j in range(len(b)):
			if a[q[i]] >= b[j]:
				cnt += 1
			else:
				break
		res[i] = cnt
	return res


def find(a, b, q):
	out = []
	for j in q:
		num = a[j]
		count = 0
		i = 0
		while i < len(b):
			if b[i] <= num:
				count += 1
			i += 1
		out.append(count)
	return out


def find(a, b, q):
	h = {i: 0 for i in range(len(a))}
	b = sorted(b)
	for i in range(len(a)):
		for j in range(len(b)):
			if a[i] >= b[j]:
				h[i] += 1
			else:
				break
	return [h[i] for i in q]


def find(a, b, q):
	l = []
	for x in q:
		c = 0
		target = a[x]
		for y in b:
			if y <= target:
				c += 1
		l.append(c)
	return l


def find(a, b, q):
	l = []

	def findcount(b, val):
		c = 0
		for i in b:
			if i <= val:
				c = c + 1
		return c
	for i in q:
		val = a[i]
		cnt = findcount(b, val)
		l.append(cnt)
	return l


def find(a, b, q):
	m = max(b)
	m2 = max(a)
	if m > m2:
		m += 1
		l = [0] * m
	else:
		m2 += 1
		l = [0] * m2
	p = []
	for i in b:
		l[i] += 1
	count = 0
	for i in l:
		count += i
		p.append(count)
	l = []
	for i in q:
		l.append(p[a[i]])
	return l


def find(a, b, q):
	b.sort()
	l = []
	for i in q:
		try:
			t = a[i]
		except IndexError:
			l.append(0)
		count = 0
		for k in b:
			if k <= t:
				count += 1
			else:
				break
		l.append(count)
		count = 0
	return l


def findCnt(b, val):
	cnt = 0
	for i in b:
		if i <= val:
			cnt += 1
	return cnt

def find(a, b, q):
	result = []
	for i in q:
		val = a[i]
		result.append(findCnt(b, val))
	return result


def find(a, b, q):
	res = []
	for i in q:
		e = a[i]
		c = 0
		for j in b:
			if j <= e:
				c += 1
		res.append(c)
	return res


def find(a, b, q):
	l = []
	for i in q:
		x = a[i]
		c = 0
		for i in b:
			if i <= x:
				c += 1
		l.append(c)
	return l


def countInB(b, ele):
	count = 0
	for i in b:
		if i <= ele:
			count += 1
	return count

def find(a, b, q):
	res = []
	for i in q:
		ele = a[i]
		res.append(countInB(b, ele))
	return res


def helper(z, b):
	count1 = 0
	for i in b:
		if i <= z:
			count1 += 1
	return count1

def find(a, b, q):
	res = []
	for i in q:
		z = a[i]
		ans = helper(z, b)
		res.append(ans)
	return res


def find(a, b, q):
	ans = []
	for i in range(len(q)):
		k = q[i]
		g = a[k]
		count = 0
		for j in range(len(b)):
			if g >= b[j]:
				count += 1
		ans.append(count)
	return ans


def find(a, b, q):
	num_elem_list = [0] * len(q)
	for (k, i) in enumerate(q):
		a_elem = a[i]
		for j in b:
			if a_elem >= j:
				num_elem_list[k] += 1
	return num_elem_list