Given two integer arrays Arr1 and Arr2 of size N. Use the greatest elements from the given arrays to create a new array of size N such that it consists of only unique elements and the sum of all its elements is maximum.
The created elements should contain the elements of Arr2 followed by elements of Arr1 in order of their appearance.
Note: The input array will be given in such way, that every time it is possible to make a new arr by maintaing the following conditions.
Example 1:
Input:
N = 5
Arr1 = {7, 4, 8, 0, 1}
Arr2 = {9, 7, 2, 3, 6}
Output: 9 7 6 4 8
Explanation: 9, 7, 6 are from 2nd array
and 4, 8 from 1st array.
Example 2:
Input: N = 4
Arr1 = {6, 7, 5, 3}
Arr2 = {5, 6, 2, 9} 
Output: 5 6 9 7 
Explanation: 5, 6, 9 are from 2nd array
and 7 from 1st array.
Your Task: 
You don't need to read input or print anything. Your task is to complete the function maximizeArray() which takes the array arr1[], arr2[] and n as input parameters and returns the desired array of integers.
Expected Time Complexity: O(NlogN)
Expected Auxiliary Space: O(N)
Constraints:
1 <= N <= 10^{5}
0 <=| Arr1[i] |<= 10^{9}
0 <= |Arr2[i] |<= 10^{9}

Difficulty: MEDIUM
Tags: Data structures

Mathematics
Skill types: Data structures
Expected Time Complexity: O(NlogN)
Expected Auxiliary Space: O(N)

Starter code:
#User function Template for python3



class Solution:

    def maximizeArray(self, arr1, arr2, n):

        # code here

Solutions:
from heapq import heappush as hp, heappop as hpo

class Solution:

	def maximizeArray(self, arr1, arr2, n):
		heap = []
		vis = set()
		for (idx, ele) in enumerate(arr2 + arr1):
			if ele not in vis:
				hp(heap, (ele, idx))
				vis.add(ele)
				if len(heap) > n:
					hpo(heap)
		return map(lambda x: x[0], sorted(heap, key=lambda x: x[1]))


class Solution:

	def maximizeArray(self, arr1, arr2, n):
		arr3 = arr1 + arr2
		arr3 = list(dict.fromkeys(arr3))
		arr3.sort(reverse=True)
		temp = {}
		for i in range(min(n, len(arr3))):
			temp[arr3[i]] = 0
		for i in range(len(arr2)):
			if arr2[i] in temp and temp[arr2[i]] == 0:
				temp[arr2[i]] = i + 1
		r_temp = {}
		for i in temp:
			if temp[i] > 0:
				r_temp[i] = temp[i]
		r_temp = sorted(r_temp.items(), key=lambda x: x[1])
		ans = []
		for i in r_temp:
			ans.append(i[0])
		r_temp.clear()
		r_temp = {}
		for i in range(len(arr1)):
			if arr1[i] in temp and temp[arr1[i]] == 0:
				temp[arr1[i]] += 1
				r_temp[arr1[i]] = i + 1
		r_temp = sorted(r_temp.items(), key=lambda x: x[1])
		for i in r_temp:
			ans.append(i[0])
		return ans


class Solution:

	def maximizeArray(self, arr1, arr2, n):
		arr11 = arr1[:]
		arr22 = arr2[:]
		arr11.sort(reverse=True)
		arr22.sort(reverse=True)
		arr11.extend(arr22)
		res = set(arr11)
		res = list(res)
		res.sort(reverse=True)
		res = res[:n]
		res = set(res)
		ans = []
		for i in arr2:
			if i in res:
				ans.append(i)
				res.remove(i)
		for i in arr1:
			if i in res:
				ans.append(i)
				res.remove(i)
		return ans


class Solution:

	def maximizeArray(self, arr1, arr2, n):
		dic = {}
		for i in range(n):
			if arr2[i] not in dic:
				dic[arr2[i]] = i
		for i in range(n):
			if arr1[i] not in dic:
				dic[arr1[i]] = n + i
		dic = sorted(dic.items(), reverse=True)[:n]
		dic = sorted(dic, key=lambda x: x[1])
		return [i[0] for i in dic]


import heapq

class Solution:

	def maximizeArray(self, arr1, arr2, n):
		arr = arr1 + arr2
		heapq._heapify_max(arr)
		maxArr = {}
		ele_count = 0
		while ele_count < n:
			if len(arr) > 0:
				x = heapq._heappop_max(arr)
			else:
				break
			if x not in maxArr:
				maxArr[x] = 1
				ele_count += 1
		li = []
		for ele in arr2:
			if maxArr.get(ele, 0) > 0:
				maxArr[ele] = 0
				li.append(ele)
		for ele in arr1:
			if maxArr.get(ele, 0) > 0:
				maxArr[ele] = 0
				li.append(ele)
		return li


class Solution:

	def maximizeArray(self, arr1, arr2, n):
		s = set()
		for i in range(n):
			s.add(arr1[i])
			s.add(arr2[i])
		s = list(s)
		s = sorted(s, reverse=True)
		while len(s) > n:
			s.pop()
		ans = list()
		s = set(s)
		for i in arr2:
			if i in s:
				s.remove(i)
				ans.append(i)
		for i in arr1:
			if i in s:
				s.remove(i)
				ans.append(i)
		return ans


class Solution:

	def maximizeArray(self, arr1, arr2, n):
		a1 = arr1[:]
		a2 = arr2[:]
		arr1.sort(reverse=True)
		arr2.sort(reverse=True)
		new = set()
		i = 0
		j = 0
		while (i < n or j < n) and len(new) < n:
			if i < n and j < n:
				if arr1[i] >= arr2[j]:
					new.add(arr1[i])
					i += 1
				else:
					new.add(arr2[j])
					j += 1
			elif i < n:
				new.add(arr1[i])
				i += 1
			elif j < n:
				new.add(arr2[j])
				j += 1
		d = {}
		ans = []
		for ele in a2:
			if ele in new and ele not in d:
				ans += [ele]
				d[ele] = 1
		for ele in a1:
			if ele in new and ele not in d:
				ans += [ele]
				d[ele] = 1
		return ans


import heapq

class Solution:

	def maximizeArray(self, arr1, arr2, n):
		s = set()
		heap = []
		for i in arr2:
			if i not in s:
				heapq.heappush(heap, i)
				s.add(i)
		for i in arr1:
			if i not in s:
				heapq.heappush(heap, i)
				s.add(i)
				if len(heap) > n:
					p = heapq.heappop(heap)
					s.remove(p)
		d = {}
		for i in heap:
			if i not in d:
				d[i] = True
		heap.clear()
		res = []
		for i in arr2:
			if i in d and d[i] != False:
				res.append(i)
				d[i] = False
		for i in arr1:
			if i in d and d[i] != False:
				res.append(i)
				d[i] = False
		return res


class Solution:

	def maximizeArray(self, arr1, arr2, n):
		res = arr1 + arr2
		res = list(set(res))
		res.sort()
		k = []
		for i in range(len(res) - 1, len(res) - n - 1, -1):
			k.append(res[i])
		d1 = {}
		d2 = {}
		result = []
		for i in k:
			if i not in d1:
				d1[i] = 1
		for i in arr2:
			if i not in d2 and i in d1:
				result.append(i)
				d2[i] = 1
		for i in arr1:
			if i not in d2 and i in d1:
				result.append(i)
				d2[i] = 1
		return result


from heapq import heappush, heappop

class Solution:

	def maximizeArray(self, a1, a2, n):
		op1 = []
		op2 = []
		unique = set()
		h1 = []
		h2 = []
		for i in range(len(a1)):
			heappush(h1, (-a1[i], i))
		for i in range(len(a2)):
			heappush(h2, (-a2[i], i))
		i = 0
		h1.sort()
		h2.sort()
		while i < n:
			if h1 and h2 and (-h1[0][0] > -h2[0][0]):
				if h1[0][0] not in unique:
					(val, ind) = heappop(h1)
					op1.append([val, ind])
					i += 1
					unique.add(val)
				else:
					heappop(h1)
			elif h1 and h2 and (-h1[0][0] <= -h2[0][0]):
				if h2[0][0] not in unique:
					(val, ind) = heappop(h2)
					op2.append([val, ind])
					i += 1
					unique.add(val)
				else:
					heappop(h2)
			elif h1:
				if h1[0][0] not in unique:
					(val, ind) = heappop(h1)
					op1.append([val, ind])
					unique.add(val)
					i += 1
				else:
					heappop(h1)
			elif h2:
				if h2[0][0] not in unique:
					(val, ind) = heappop(h2)
					op2.append([val, ind])
					unique.add(val)
					i += 1
				else:
					heappop(h2)
			else:
				break
		op1 = sorted(op1, key=lambda x: x[1])
		op2 = sorted(op2, key=lambda x: x[1])
		ans = []
		for (val, ind) in op2:
			ans.append(-val)
		for (val, ind) in op1:
			ans.append(-val)
		return ans


from heapq import heappush as push, heappop as pop
from bisect import insort

class Solution:

	def maximizeArray(self, arr1, arr2, n):
		h = []
		(sel1, sel2) = ([], [])
		for (i, v) in enumerate(arr2):
			push(h, (-v, 1, i))
		for (i, v) in enumerate(arr1):
			push(h, (-v, 2, i))
		prev = 1000
		i = 0
		while i < n and len(h) > 0:
			(v, t, j) = pop(h)
			if v == prev:
				continue
			if t == 2:
				insort(sel1, (j, -v))
			else:
				insort(sel2, (j, -v))
			prev = v
			i += 1
		ans = []
		sel2.extend(sel1)
		for i in sel2:
			ans.append(i[1])
		return ans


from collections import OrderedDict

class Solution:

	def maximizeArray(self, arr1, arr2, n):
		items = sorted(set(arr1 + arr2))[-n:]
		result = []
		for item in arr2:
			if item >= items[0]:
				result.append(item)
		for item in arr1:
			if item >= items[0]:
				result.append(item)
		return list(OrderedDict.fromkeys(result))


class Solution:

	def maximizeArray(self, arr1, arr2, n):
		arr3 = arr1 + arr2
		new_arr3 = list(set(arr3))
		new_arr3.sort(reverse=True)
		d = {i: 0 for i in new_arr3[:n]}
		ans = []
		for i in range(n):
			if arr2[i] in d:
				ans.append(arr2[i])
				del d[arr2[i]]
		for i in range(n):
			if arr1[i] in d:
				ans.append(arr1[i])
				del d[arr1[i]]
		return ans


class Solution:

	def maximizeArray(self, arr1, arr2, n):
		arr3 = arr2 + arr1
		a = arr3
		arr3 = list(set(arr3))
		arr3 = sorted(arr3)
		r = []
		res = list(reversed(arr3))
		check = set()
		res = set(res[0:n])
		for i in a:
			if i in res and i not in check:
				check.add(i)
				r.append(i)
		return r


class Solution:

	def maximizeArray(self, arr1, arr2, n):
		a1 = arr2 + arr1
		a3 = list(set(a1))
		a3.sort(reverse=True)
		a4 = set(a3[:n])
		check = set()
		res = []
		for i in range(2 * n):
			if len(res) == n:
				return res
			if a1[i] in a4 and a1[i] not in check:
				res.append(a1[i])
				check.add(a1[i])
		return res


class Solution:

	def maximizeArray(self, arr1, arr2, n):
		arr = arr1 + arr2
		new = []
		arr = list(set(arr))
		arr.sort(reverse=True)
		s = set(arr[:n])
		punk = set()
		for i in range(len(arr2)):
			if arr2[i] in s and arr2[i] not in punk:
				new.append(arr2[i])
				punk.add(arr2[i])
		for i in range(len(arr1)):
			if arr1[i] in s and arr1[i] not in punk:
				new.append(arr1[i])
				punk.add(arr1[i])
		return new


from heapq import heapify, heappop, heappush

class Solution:

	def maximizeArray(self, arr1, arr2, n):
		c = []
		m = {}
		for i in arr1:
			if i not in m:
				m[i] = 2
				heappush(c, -i)
		for i in arr2:
			if i not in m:
				m[i] = 2
				heappush(c, -i)
		for i in range(n):
			try:
				m[-heappop(c)] = 1
			except:
				break
		d = []
		for i in arr2:
			if m[i] == 1:
				d.append(i)
				m[i] = 0
		for i in arr1:
			if m[i] == 1:
				d.append(i)
				m[i] = 0
		return d


import heapq

class MinHeapItem:

	def __init__(self, val, aind, vind):
		self.val = val
		self.aind = aind
		self.vind = vind

	def __lt__(self, other):
		return self.val < other.val

class Solution:

	def maximizeArray(self, arr1, arr2, n):
		minHeap = []
		outset = set()
		for i in range(len(arr2)):
			if arr2[i] not in outset:
				if len(minHeap) < n:
					heapq.heappush(minHeap, MinHeapItem(arr2[i], 2, i))
					outset.add(arr2[i])
				elif arr2[i] > minHeap[0].val:
					top = heapq.heapreplace(minHeap, MinHeapItem(arr2[i], 2, i))
					outset.add(arr2[i])
					outset.remove(top.val)
		for i in range(len(arr1)):
			if arr1[i] not in outset:
				if len(minHeap) < n:
					heapq.heappush(minHeap, MinHeapItem(arr1[i], 1, i))
					outset.add(arr1[i])
				elif arr1[i] > minHeap[0].val:
					top = heapq.heapreplace(minHeap, MinHeapItem(arr1[i], 1, i))
					outset.add(arr1[i])
					outset.remove(top.val)
		minHeap.sort(key=lambda x: x.vind)
		minHeap.sort(key=lambda x: x.aind, reverse=True)
		return [i.val for i in minHeap]


from collections import OrderedDict

class Solution:

	def maximizeArray(self, arr1, arr2, n):
		final = []
		ar = {}
		arr = sorted(list(set(arr1 + arr2)))[::-1]
		arr = arr[:n]
		for i in arr:
			ar[i] = 1
		i = 0
		while i != n:
			if arr2[i] in ar:
				del ar[arr2[i]]
				final.append(arr2[i])
			i += 1
		i = 0
		while i != n:
			if arr1[i] in ar:
				del ar[arr1[i]]
				final.append(arr1[i])
			i += 1
		return final


class Solution:

	def maximizeArray(self, arr1, arr2, n):
		a = []
		b = []
		ar = {}
		arr = sorted(list(set(arr1 + arr2)))[::-1]
		arr = arr[:n]
		final = []
		for i in arr:
			ar[i] = 1
		i = 0
		while i != n:
			if arr2[i] in ar:
				del ar[arr2[i]]
				final.append(arr2[i])
			i += 1
		i = 0
		while i != n:
			if arr1[i] in ar:
				del ar[arr1[i]]
				final.append(arr1[i])
			i += 1
		return final


class Solution:

	def maximizeArray(self, arr1, arr2, n):
		A = [(i, v) for (i, v) in enumerate(arr1)]
		B = [(i, v) for (i, v) in enumerate(arr2)]
		A.sort(key=lambda x: (-x[1], x[0]))
		B.sort(key=lambda x: (-x[1], x[0]))
		(ans1, ans2) = ([], [])
		(i, j, prev, cnt) = (0, 0, -1, 0)
		while cnt < n:
			v0 = A[i][1] if i < n else -1
			v1 = B[j][1] if j < n else -1
			if v0 == -1 and v1 == -1:
				break
			if v0 > v1:
				if v0 != prev:
					ans1.append(A[i])
					prev = v0
					cnt += 1
				i += 1
			else:
				if v1 != prev:
					ans2.append(B[j])
					prev = v1
					cnt += 1
				j += 1
		ans1.sort()
		ans2.sort()
		ans = [v[1] for v in ans2] + [v[1] for v in ans1]
		return ans


class Solution:

	def maximizeArray(self, arr1, arr2, n):
		ans = [0] * n
		from heapq import heappush, heappop
		lis = list()
		di = dict()
		for i in range(n):
			di[arr2[i]] = di.get(arr2[i], 0) + 1
			if di[arr2[i]] == 1:
				lis.append([0, arr2[i], i])
		for i in range(n):
			di[arr1[i]] = di.get(arr1[i], 0) + 1
			if di[arr1[i]] == 1:
				lis.append([1, arr1[i], i])
		lis.sort(key=lambda x: x[1], reverse=True)
		(ans1, ans2) = (list(), list())
		try:
			for i in range(n):
				if lis[i][0] == 0:
					ans1.append([lis[i][1], lis[i][2]])
				else:
					ans2.append([lis[i][1], lis[i][2]])
		except:
			pass
		ans1.sort(key=lambda x: x[1])
		ans2.sort(key=lambda x: x[1])
		for i in range(len(ans1)):
			ans1[i] = ans1[i][0]
		for i in range(len(ans2)):
			ans2[i] = ans2[i][0]
		ans = ans1 + ans2
		return ans


import heapq

class Solution:

	def maximizeArray(self, arr1, arr2, n):
		arr = sorted(list(set(arr1 + arr2)))[::-1]
		arr = arr[:n]
		dict1 = {}
		final = []
		for i in arr:
			dict1[i] = 1
		i = 0
		while i != n:
			if arr2[i] in dict1:
				del dict1[arr2[i]]
				final.append(arr2[i])
			i += 1
		i = 0
		while i != n:
			if arr1[i] in dict1:
				del dict1[arr1[i]]
				final.append(arr1[i])
			i += 1
		return final


class Solution:

	def maximizeArray(self, arr1, arr2, n):
		arr3 = arr1 + arr2
		arr3 = list(dict.fromkeys(arr3))
		arr3.sort(reverse=True)
		temp = {}
		for i in range(min(n, len(arr3))):
			temp[arr3[i]] = 0
		for i in range(len(arr2)):
			if arr2[i] in temp and temp[arr2[i]] == 0:
				temp[arr2[i]] = i + 1
		r_temp = {}
		for i in temp:
			if temp[i] > 0:
				r_temp[i] = temp[i]
		r_temp = sorted(r_temp.items(), key=lambda x: x[1])
		ans = []
		for i in r_temp:
			ans.append(i[0])
		r_temp.clear()
		r_temp = {}
		for i in range(len(arr1)):
			if arr1[i] in temp and temp[arr1[i]] == 0:
				temp[arr1[i]] += 1
				r_temp[arr1[i]] = i + 1
		r_temp = sorted(r_temp.items(), key=lambda x: x[1])
		for i in r_temp:
			ans.append(i[0])
		return ans
if __name__ == '__main__':
	tc = int(input())
	while tc > 0:
		n = int(input().strip())
		arr1 = list(map(int, input().strip().split()))
		arr2 = list(map(int, input().strip().split()))
		ob = Solution()
		ans = ob.maximizeArray(arr1, arr2, n)
		for i in ans:
			print(i, end=' ')
		print()
		tc -= 1


class Solution:

	def maximizeArray(self, arr1, arr2, n):
		a1p = n - 1
		a2p = 0
		p1 = 0
		p2 = 0
		sett = set()
		arr = list(set(arr1 + arr2))
		arr.sort(reverse=True)
		sett = set(arr[:n])
		marr = []
		for i in range(n):
			if arr2[i] in sett:
				marr.append(arr2[i])
				sett.remove(arr2[i])
		for i in range(n):
			if arr1[i] in sett:
				marr.append(arr1[i])
				sett.remove(arr1[i])
		return marr


from heapq import heappop, heappush

class Solution:

	def maximizeArray(self, arr1, arr2, n):
		minHeap = []
		visited = set()
		for (index, value) in enumerate(arr2 + arr1):
			if value not in visited:
				heappush(minHeap, (value, index))
				visited.add(value)
				if len(minHeap) > n:
					heappop(minHeap)
		return [pair[0] for pair in sorted(minHeap, key=lambda x: x[1])]


from heapq import heappush, heappop

class Solution:

	def maximizeArray(self, arr1, arr2, n):
		new = arr2 + arr1
		heap = []
		set_ = set()
		for (i, j) in enumerate(new):
			if j not in set_:
				heappush(heap, (j, i))
				set_.add(j)
				if len(heap) > n:
					heappop(heap)
		return [x[0] for x in sorted(heap, key=lambda x: x[1])]


class Solution:

	def maximizeArray(self, arr1, arr2, n):
		from collections import defaultdict
		panku = arr2 + arr1
		dic = defaultdict(lambda : -1)
		for i in range(2 * n):
			if dic[panku[i]] == -1:
				dic[panku[i]] = i
		panku.sort(reverse=True)
		ans = [panku[0]]
		count = 1
		for i in range(1, 2 * n):
			if count == n:
				break
			if ans[-1] != panku[i]:
				ans.append(panku[i])
				count += 1
		ans.sort(key=lambda x: dic[x])
		return ans


class Solution:

	def maximizeArray(self, arr1, arr2, n):
		from collections import defaultdict
		x = sorted(list(set(arr1 + arr2)), reverse=True)
		if n > len(x):
			curr_sum = x[-1]
		else:
			curr_sum = x[n - 1]
		dic = defaultdict(int)
		ans = []
		for i in arr2:
			if i >= curr_sum and (dic[i] == 0 or len(ans) == 0):
				dic[i] = 1
				ans.append(i)
		for i in arr1:
			if i >= curr_sum and (dic[i] == 0 or len(ans) == 0):
				dic[i] = 1
				ans.append(i)
		return ans


import heapq as hq

class Solution:

	def maximizeArray(self, arr1, arr2, n):
		temp = []
		d = dict()
		for i in arr2:
			if i not in d:
				hq.heappush(temp, i)
				d[i] = True
			if len(temp) > n:
				hq.heappop(temp)
		for i in arr1:
			if i not in d:
				hq.heappush(temp, i)
				d[i] = True
			if len(temp) > n:
				hq.heappop(temp)
		ans = []
		d = dict()
		for i in temp:
			d[i] = True
		for i in arr2:
			if i in d and d[i]:
				ans.append(i)
				d[i] = False
		for i in arr1:
			if i in d and d[i]:
				ans.append(i)
				d[i] = False
		return ans


class Solution:

	def maximizeArray(self, arr1, arr2, n):
		arr3 = arr1 + arr2
		s = set(arr3)
		arr3 = list(s)
		arr3.sort()
		arr3.reverse()
		hm = {}
		for i in range(n):
			if i < len(arr3):
				hm[arr3[i]] = 1
		arr4 = []
		for i in range(n):
			if hm.get(arr2[i]):
				arr4.append(arr2[i])
				hm[arr2[i]] = 0
		for i in range(n):
			if hm.get(arr1[i]):
				arr4.append(arr1[i])
				hm[arr1[i]] = 0
		return arr4


import heapq as h

class Solution:

	def maximizeArray(self, arr1, arr2, n):
		l = []
		h.heapify(l)
		for i in range(len(arr1)):
			h.heappush(l, [-arr1[i], 2, i])
		for i in range(len(arr2)):
			h.heappush(l, [-arr2[i], 1, i])
		l1 = []
		l2 = []
		count = 0
		g1 = dict()
		while count < n and len(l) > 0:
			x = h.heappop(l)
			if g1.get(-x[0]) != None:
				continue
			if x[1] == 1:
				l1.append([x[2], -x[0]])
			if x[1] == 2:
				l2.append([x[2], -x[0]])
			g1[-x[0]] = True
			count = count + 1
		l1.sort()
		l2.sort()
		l3 = []
		for i in l1:
			l3.append(i[1])
		for i in l2:
			l3.append(i[1])
		return l3


class Solution:

	def maximizeArray(self, arr1, arr2, n):
		l = sorted(list(set(arr1 + arr2)), reverse=True)[:n]
		l = set(l)
		ans = []
		vs = set()
		for i in arr2:
			if i in l and i not in vs:
				ans.append(i)
				vs.add(i)
		for i in arr1:
			if i in l and i not in vs:
				ans.append(i)
				vs.add(i)
		return ans


import heapq

class Solution:

	def maximizeArray(self, arr1, arr2, N):
		map1 = dict()
		res = []
		res1 = []
		ans = []
		for i in range(N):
			if arr2[i] not in map1:
				map1[arr2[i]] = [i, 'arr2']
		for i in range(N):
			if arr1[i] not in map1:
				map1[arr1[i]] = [i, 'arr1']
		n = len(map1)
		if n < N:
			N = n
		arr1 = [[key, val[0], val[1]] for (key, val) in map1.items()]
		arr = arr1[:N]
		heapq.heapify(arr)
		for i in range(N, len(arr1)):
			if arr1[i][0] > arr[0][0]:
				heapq.heappop(arr)
				heapq.heappush(arr, arr1[i])
		for i in range(N):
			if arr[i][2] == 'arr2':
				res.append([arr[i][1], arr[i][0]])
		heapq.heapify(res)
		while len(res) != 0:
			val = heapq.heappop(res)
			ans.append(val[1])
		for i in range(N):
			if arr[i][2] == 'arr1':
				res1.append([arr[i][1], arr[i][0]])
		heapq.heapify(res1)
		while len(res1) != 0:
			val = heapq.heappop(res1)
			ans.append(val[1])
		return ans


class Solution:

	def maximizeArray(self, arr1, arr2, n):
		arr1 = [(arr1[i], i) for i in range(n)]
		arr2 = [(arr2[i], i) for i in range(n)]
		i = n - 1
		i1 = n - 1
		i2 = n - 1
		ans1 = []
		ans2 = []
		arr1.sort(key=lambda x: (x[0], -x[1]))
		arr2.sort(key=lambda x: (x[0], -x[1]))
		while i >= 0 and i1 >= 0 and (i2 >= 0):
			if arr1[i1][0] > arr2[i2][0]:
				ans1.append(arr1[i1])
				i1 -= 1
				while i1 >= 0 and arr1[i1][0] == arr1[i1 + 1][0]:
					i1 -= 1
				i -= 1
			elif arr1[i1][0] < arr2[i2][0]:
				ans2.append(arr2[i2])
				i2 -= 1
				while i2 >= 0 and arr2[i2][0] == arr2[i2 + 1][0]:
					i2 -= 1
				i -= 1
			else:
				ans2.append(arr2[i2])
				i2 -= 1
				i -= 1
				i1 -= 1
				while i1 >= 0 and arr1[i1][0] == arr1[i1 + 1][0]:
					i1 -= 1
				while i2 >= 0 and arr2[i2][0] == arr2[i2 + 1][0]:
					i2 -= 1
		while i >= 0 and i1 >= 0:
			ans1.append(arr1[i1])
			i1 -= 1
			while i1 >= 0 and arr1[i1][0] == arr1[i1 + 1][0]:
				i1 -= 1
			i -= 1
		while i >= 0 and i2 >= 0:
			ans2.append(arr2[i2])
			i2 -= 1
			while i2 >= 0 and arr2[i2][0] == arr2[i2 + 1][0]:
				i2 -= 1
			i -= 1
		ans1.sort(key=lambda x: x[1])
		ans2.sort(key=lambda x: x[1])
		ans = []
		for val in ans2:
			ans.append(val[0])
		for val in ans1:
			ans.append(val[0])
		return ans


class Solution:

	def maximizeArray(self, arr1, arr2, n):
		mp = {}
		res1 = []
		res2 = []
		for i in arr2:
			if i not in mp:
				mp[i] = 1
				res1.append(i)
				res2.append(i)
		for i in arr1:
			if i not in mp:
				mp[i] = 1
				res1.append(i)
				res2.append(i)
		res2.sort(reverse=True)
		if len(res1) <= n:
			return res1
		else:
			d = {}
			for i in range(n):
				d[res2[i]] = 1
			ans = []
			for i in range(len(res1)):
				if res1[i] in d:
					ans.append(res1[i])
			return ans


class Solution:

	def maximizeArray(self, a1, a2, n):
		arr1 = sorted(list(set(a1)))
		arr2 = sorted(list(set(a2)))
		dd = {}
		ee = {}
		d = []
		for i in range(n):
			if arr1 == [] and arr2 == []:
				break
			if arr1 == []:
				x = arr2.pop()
				ee[x] = 1
			elif arr2 == []:
				x = arr1.pop()
				dd[x] = 1
			elif arr1[-1] == arr2[-1]:
				x = arr1.pop()
				ee[x] = 1
				arr2.pop()
			elif arr1[-1] > arr2[-1]:
				x = arr1.pop()
				dd[x] = 1
			else:
				x = arr2.pop()
				ee[x] = 1
		for i in a2:
			if ee.get(i, 0) == 1:
				ee[i] = 0
				d.append(i)
		for i in a1:
			if dd.get(i, 0) == 1:
				dd[i] = 0
				d.append(i)
		return d


class Solution:

	def maximizeArray(self, arr1, arr2, n):
		arr3 = [0] * (2 * n)
		k = 0
		for i in range(n):
			arr3[k] = arr1[i]
			k += 1
		for i in range(n):
			arr3[k] = arr2[i]
			k += 1
		arr3.sort(reverse=True)
		hs = {}
		i = 0
		while len(hs) != n and i < 2 * n:
			if arr3[i] not in hs:
				hs[arr3[i]] = 1
			i += 1
		ans = []
		for i in range(n):
			if arr2[i] in hs:
				ans.append(arr2[i])
				del hs[arr2[i]]
		for i in range(n):
			if arr1[i] in hs:
				ans.append(arr1[i])
				del hs[arr1[i]]
		return ans


from collections import defaultdict as df

class Solution:

	def maximizeArray(self, arr1, arr2, n):
		arr = arr2 + arr1
		s = list(set(arr))
		s.sort(reverse=True)
		num = s[:n]
		ans = []
		d = df(int)
		for i in range(len(num)):
			d[num[i]] = 1
		for i in range(len(arr)):
			if d[arr[i]] == 1:
				ans.append(arr[i])
				d[arr[i]] = 0
		return ans


class Solution:

	def maximizeArray(self, arr1, arr2, n):
		arr = sorted(arr1 + arr2, reverse=True)
		count = 1
		prev = arr[0]
		for (i, num) in enumerate(arr):
			if num != prev:
				count += 1
				prev = num
			if count == n:
				break
		ans = []
		set_ans = set()
		for i in arr2:
			if i >= prev:
				if i not in set_ans:
					set_ans.add(i)
					ans.append(i)
		for i in arr1:
			if i >= prev:
				if i not in set_ans:
					set_ans.add(i)
					ans.append(i)
		return ans


import heapq

class Solution:

	def maximizeArray(self, arr1, arr2, n):
		heap = []
		s = set()
		for (i, ele) in enumerate(arr2 + arr1):
			if ele not in s:
				heapq.heappush(heap, [ele, i])
				s.add(ele)
				if len(heap) > n:
					heapq.heappop(heap)
		return [i[0] for i in sorted(heap, key=lambda i: i[1])]


import heapq

class Solution:

	def maximizeArray(self, arr1, arr2, n):
		heap = []
		exists = set()
		for (i, x) in enumerate(arr2 + arr1):
			if x not in exists:
				heapq.heappush(heap, (x, i))
				exists.add(x)
				if len(heap) > n:
					heapq.heappop(heap)
		return [t[0] for t in sorted(heap, key=lambda t: t[1])]


class Solution:

	def maximizeArray(self, arr1, arr2, n):
		ans = arr1 + arr2
		ans.sort(reverse=True)
		st = set()
		i = 0
		while i < n + n and len(st) < n:
			st.add(ans[i])
			i += 1
		finalarr = []
		for i in arr2:
			if i in st:
				finalarr.append(i)
				st.remove(i)
		for i in arr1:
			if i in st:
				finalarr.append(i)
				st.remove(i)
		return finalarr[:n]


class Solution:

	def maximizeArray(self, arr1, arr2, n):
		r = []
		a = sorted([(e, 1, i) for (i, e) in enumerate(arr2)] + [(e, 2, i) for (i, e) in enumerate(arr1)], key=lambda x: -x[0])
		s = set()
		for (x, y, z) in a:
			if x not in s:
				r.append((x, y, z))
				s.add(x)
			if len(r) == n:
				break
		r.sort(key=lambda x: (x[1], x[2]))
		return [e[0] for e in r]


class Solution:

	def maximizeArray(self, arr1, arr2, n):
		arr3 = [0] * (2 * n)
		k = 0
		for i in range(n):
			arr3[k] = arr1[i]
			k += 1
		for i in range(n):
			arr3[k] = arr2[i]
			k += 1
		hash = {}
		arr3 = sorted(arr3)
		arr3 = arr3[::-1]
		i = 0
		while len(hash) != n and i < len(arr3):
			if arr3[i] not in hash:
				hash[arr3[i]] = 1
			i += 1
		kk = len(hash)
		k = 0
		for i in range(n):
			if arr2[i] in hash:
				arr3[k] = arr2[i]
				k += 1
				del hash[arr2[i]]
		for i in range(n):
			if arr1[i] in hash:
				arr3[k] = arr1[i]
				k += 1
				del hash[arr1[i]]
		return arr3[:kk]


from heapq import heapify, heappush, heappop

class Solution:

	def maximizeArray(self, arr1, arr2, n):
		arr3 = [0] * (2 * n)
		for i in arr1:
			arr3.append(i)
		for j in arr2:
			arr3.append(j)
		arr3.sort(reverse=True)
		dic = {}
		k = 0
		while len(dic) < n:
			if k >= 2 * n:
				break
			dic[arr3[k]] = True
			k += 1
		ans = []
		for i in range(n):
			if arr2[i] in dic:
				ans.append(arr2[i])
				del dic[arr2[i]]
		for i in range(n):
			if arr1[i] in dic:
				ans.append(arr1[i])
				del dic[arr1[i]]
		return ans


class Solution:

	def maximizeArray(self, arr1, arr2, n):
		arr = arr1 + arr2
		arr.sort()
		s = set()
		for i in range(2 * n - 1, -1, -1):
			if len(s) < n:
				s.add(arr[i])
		result = []
		for i in arr2:
			if i in s:
				result.append(i)
				s.remove(i)
		for i in arr1:
			if i in s:
				result.append(i)
				s.remove(i)
		return result


class Solution:

	def maximizeArray(self, arr1, arr2, n):
		a = []
		res = []
		d = dict()
		for i in range(n):
			if arr2[i] not in d:
				d[arr2[i]] = 1
				a.append([arr2[i], i, 2])
		for i in range(n):
			if arr1[i] not in d:
				d[arr1[i]] = 1
				a.append([arr1[i], i, 1])
		a = sorted(a, key=lambda a: -a[0])
		res1 = []
		res2 = []
		l = len(a)
		if l > n:
			l = n
		for i in range(l):
			if a[i][2] == 1:
				res1.append(a[i])
			else:
				res2.append(a[i])
		res1 = sorted(res1, key=lambda a: a[1])
		res2 = sorted(res2, key=lambda a: a[1])
		for r in res2:
			res.append(r[0])
		for r in res1:
			res.append(r[0])
		return res


class Solution:

	def maximizeArray(self, arr1, arr2, n):
		bothset = set(arr1)
		bothset.update(arr2)
		botharr = list(bothset)
		botharr.sort(reverse=True)
		botharr = botharr[0:n]
		reqset = set(botharr)
		ans = []
		ansi = 0
		used = set()
		for n in arr2:
			if n in reqset and (not n in used):
				used.add(n)
				ans.append(n)
				ansi += 1
		for n in arr1:
			if n in reqset and (not n in used):
				used.add(n)
				ans.append(n)
				ansi += 1
		return ans


class Solution:

	def maximizeArray(self, arr1, arr2, n):
		(h1, h2) = (dict(), dict())
		for i in range(n):
			if arr1[i] not in h1:
				h1[arr1[i]] = i
		for j in range(n):
			if arr2[j] not in h2:
				h2[arr2[j]] = j
		arr1.sort(reverse=True)
		arr2.sort(reverse=True)
		res1 = [-1] * n
		res2 = [-1] * n
		(i, j) = (0, 0)
		c = 0
		while i < n and j < n and (c < n):
			if arr1[i] > arr2[j]:
				res1[h1[arr1[i]]] = arr1[i]
				k = i
				while k < n - 1 and arr1[k] == arr1[k + 1]:
					k += 1
				i = k + 1
				c += 1
			elif arr1[i] < arr2[j]:
				res2[h2[arr2[j]]] = arr2[j]
				k = j
				while k < n - 1 and arr2[k] == arr2[k + 1]:
					k += 1
				j = k + 1
				c += 1
			else:
				res2[h2[arr2[j]]] = arr2[j]
				k = i
				while k < n - 1 and arr1[k] == arr1[k + 1]:
					k += 1
				i = k + 1
				k = j
				while k < n - 1 and arr2[k] == arr2[k + 1]:
					k += 1
				j = k + 1
				c += 1
		if c < n:
			if i < n:
				while i < n and c < n:
					res1[h1[arr1[i]]] = arr1[i]
					k = i
					while k < n - 1 and arr1[k] == arr1[k + 1]:
						k += 1
					i = k + 1
					c += 1
			else:
				while j < n and c < n:
					res2[h2[arr2[j]]] = arr2[j]
					k = j
					while k < n - 1 and arr2[k] == arr2[k + 1]:
						k += 1
					j = k + 1
					c += 1
		res = []
		for j in range(n):
			if res2[j] != -1:
				res.append(res2[j])
		for i in range(n):
			if res1[i] != -1:
				res.append(res1[i])
		return res


import heapq

class Solution:

	def maximizeArray(self, arr1, arr2, n):
		arr3 = []
		for i in range(len(arr1)):
			arr3.append(arr1[i])
		for i in range(len(arr2)):
			arr3.append(arr2[i])
		arr3 = sorted(arr3)
		arr3 = arr3[::-1]
		dict_ = {}
		i = 0
		k = 0
		res = []
		while i < n and k < 2 * n:
			if arr3[k] not in dict_:
				dict_[arr3[k]] = 1
				i += 1
			k += 1
		for i in range(len(arr2)):
			if arr2[i] in dict_:
				res.append(arr2[i])
				del dict_[arr2[i]]
		for i in range(len(arr1)):
			if arr1[i] in dict_:
				res.append(arr1[i])
				del dict_[arr1[i]]
		return res


from collections import defaultdict

class Solution:

	def maximizeArray(self, arr1, arr2, n):
		res = set()
		ans = []
		bigarr = arr1 + arr2
		bigarr = set(bigarr)
		bigarr = sorted(bigarr)
		hash1 = defaultdict(lambda : 0)
		hash2 = defaultdict(lambda : 0)
		dupi_hash2 = defaultdict(lambda : 0)
		for ele in arr2:
			dupi_hash2[ele] = 1
		for ele in arr2:
			hash2[ele] = 1
		for ele in arr1:
			hash1[ele] = 1
		i = len(bigarr) - 1
		while len(res) < n and i >= 0:
			res.add(bigarr[i])
			i -= 1
		for ele in arr2:
			if ele in res and hash2[ele] == 1:
				ans.append(ele)
				hash2[ele] = 0
		for ele in arr1:
			if ele in res and dupi_hash2[ele] == 0 and (hash1[ele] == 1):
				ans.append(ele)
				hash1[ele] = 0
		return ans


class Solution:

	def maximizeArray(self, arr1, arr2, n):
		temp = []
		for i in range(n):
			temp.append(arr1[i])
			temp.append(arr2[i])
		temp.sort(reverse=True)
		s = set()
		j = 0
		while len(s) < n and j < 2 * n:
			s.add(temp[j])
			j += 1
		check = set()
		ans = []
		for x in arr2:
			if x in s and x not in check:
				ans.append(x)
				check.add(x)
		for y in arr1:
			if y in s and y not in check:
				ans.append(y)
				check.add(y)
		return ans


class Solution:

	def maximizeArray(self, arr1, arr2, n):
		both = []
		for i in range(n):
			both.append((arr2[i], 2, i))
		for i in range(n):
			both.append((arr1[i], 1, i))
		both.sort(key=lambda x: x[0], reverse=True)
		s = set()
		mid = []
		for i in both:
			if i[0] not in s:
				mid.append(i)
				s.add(i[0])
		srr1 = []
		srr2 = []
		for i in range(min(len(mid), n)):
			if mid[i][1] == 2:
				srr2.append(mid[i])
			else:
				srr1.append(mid[i])
		srr1.sort(key=lambda x: x[2])
		srr2.sort(key=lambda x: x[2])
		return [i[0] for i in srr2 + srr1]


from heapq import heappush, heappop

class Solution:

	def maximizeArray(self, arr1, arr2, n):
		added_nums = set()
		heap = []
		for (idx, val) in enumerate(arr2 + arr1):
			if val not in added_nums:
				added_nums.add(val)
				heappush(heap, (val, idx))
				if len(heap) > n:
					heappop(heap)
		heap.sort(key=lambda x: x[1])
		ans = [x[0] for x in heap]
		return ans