You are given two  arrays, $\mbox{A}$ and $\mbox{B}$, both containing $N$ integers.

A pair of indices $(i,j)$ is beautiful if the $i^{\mbox{th}}$ element of array $\mbox{A}$ is equal to the $j^{th}$ element of array $\mbox{B}$. In other words, pair $(i,j)$ is beautiful if and only if $A[i]=B[j]$. A set containing beautiful pairs is called a beautiful set.

A beautiful set is called pairwise disjoint if for every pair $\left(l[i],r[i]\right)$ belonging to the set there is no repetition of either $l\left[i\right]$ or $r[i]$ values. For instance, if $A=[10,11,12,5,14]$ and $B=[8,9,11,11,5]$ the beautiful set $[(1,2),(1,3),(3,4)]$ is not pairwise disjoint as there is a repetition of $\mbox{I}$, that is $l[\textbf{0}][\textbf{0}]=l[1][\textbf{0}]$. 

Your task is to change exactly $1$ element in $\mbox{B}$ so that the size of the pairwise disjoint beautiful set is maximum.

Function Description  

Complete the beautifulPairs function in the editor below.  It should return an integer that represents the maximum number of pairwise disjoint beautiful pairs that can be formed.  

beautifulPairs has the following parameters:  

A: an array of integers  
B: an array of integers  

Input Format

The first line contains a single integer $n$, the number of elements in $\mbox{A}$ and $\mbox{B}$. 

The second line contains $n$ space-separated integers $A[i]$. 

The third line contains $n$ space-separated integers $B[i]$.

Constraints

$1\leq n\leq10^3$
$1\leq A[i],B[i]\leq10^3$

Output Format

Determine and print the maximum possible number of pairwise disjoint beautiful pairs. 

Note: You must first change $1$ element in $\mbox{B}$, and your choice of element must be optimal.

Sample Input 0
4
1 2 3 4
1 2 3 3

Sample Output 0
4

Explanation 0

You are given $A=[1,2,3,4]$ and $B=[1,2,3,3]$. 

The beautiful set is $[(0,0),(1,1),(2,2),(2,3)]$ and maximum sized pairwise disjoint beautiful set is either $[(0,0),(1,1),(2,2)]$ or $[(0,0),(1,1),(2,3)]$. 

We can do better. We change the $3^{rd}$ element of array $\mbox{B}$ from $3$ to $4$. Now new B array is: $B=[1,2,4,3]$ and the pairwise disjoint beautiful set is $[(0,0),(1,1),(2,3),(3,2)]$. So, the answer is 4. 

Note that we could have also selected index 3 instead of index 2 but it would have yeilded the same result. Any other choice of index is not optimal.

Sample Input 1
6
3 5 7 11 5 8
5 7 11 10 5 8

Sample Output 1
6

Difficulty: EASY
Tags: Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
input()
a = [x for x in input().split()]
b = [x for x in input().split()]
aDict = dict()
bDict = dict()
for val in a:
	if val in aDict:
		aDict[val] += 1
	else:
		aDict[val] = 1
for val in b:
	if val in bDict:
		bDict[val] += 1
	else:
		bDict[val] = 1
total = 0
for val in aDict:
	while aDict[val] > 0 and val in bDict and (bDict[val] > 0):
		total += 1
		aDict[val] -= 1
		bDict[val] -= 1
if total == len(a):
	print(total - 1)
else:
	print(total + 1)


import functools
import itertools
import operator
from collections import Counter

def main():
	n = int(input())
	a_arr = [int(x) for x in input().strip().split(' ')]
	b_arr = [int(x) for x in input().strip().split(' ')]
	a_cnt = Counter(a_arr)
	b_cnt = Counter(b_arr)
	pairs_count = 0
	for (elem, val) in a_cnt.items():
		if elem in b_cnt:
			pairs_count += min(val, b_cnt[elem])
	if not a_cnt == b_cnt:
		pairs_count += 1
	else:
		pairs_count -= 1
	print(pairs_count)
main()


from collections import Counter
n = int(input())
A = input().split()
B = input().split()
a = Counter(A)
pairs = 0
leftover = None
for b in B:
	if b in a and a[b] > 0:
		pairs += 1
		a[b] -= 1
	else:
		leftover = b
if leftover != None:
	pairs += 1
else:
	pairs -= 1
print(pairs)


def get_max_beautiful_pairs(list_a, list_b):
	sorted_a = sorted(list_a)
	sorted_b = sorted(list_b)
	if sorted_a == sorted_b:
		return len(sorted_a) - 1
	num_matches = 0
	index_a = 0
	index_b = 0
	while index_a < len(list_a) and index_b < len(list_b):
		if sorted_a[index_a] == sorted_b[index_b]:
			num_matches += 1
			index_a += 1
			index_b += 1
		elif sorted_a[index_a] < sorted_b[index_b]:
			index_a += 1
		else:
			index_b += 1
	return num_matches + 1
_ = input()
list_a = [int(_val) for _val in input().strip().split()]
list_b = [int(_val) for _val in input().strip().split()]
print(get_max_beautiful_pairs(list_a, list_b))


n = int(input())
A = input().split()
B = input().split()
result = []
for (j, b) in enumerate(B):
	if b in A:
		i = A.index(b)
		result.append((i, j))
		A.pop(i)
count = len(result)
if count < n:
	print(count + 1)
else:
	print(count - 1)


N = int(input())
A = [int(a) for a in input().split()]
B = [int(b) for b in input().split()]
bp = 0
for b in list(B):
	if b in A:
		B.remove(b)
		A.remove(b)
		bp += 1
if len(B) == 0:
	bp -= 1
else:
	bp += 1
print(bp)


from collections import Counter
import sys
__author__ = 'namii'

def solve_beautiful(A, B):
	a_count = Counter(A)
	b_count = Counter(B)
	for key in a_count:
		b_count[key] -= a_count[key]
	mis_matches = sum([x for x in b_count.values() if x > 0])
	if mis_matches > 0:
		mis_matches -= 1
	else:
		mis_matches += 1
	print(len(A) - mis_matches)

def main(inp=sys.stdin):
	N = int(inp.readline().strip())
	A = [int(x) for x in inp.readline().strip().split(' ')]
	B = [int(x) for x in inp.readline().strip().split(' ')]
	solve_beautiful(A, B)

def test_main():
	main(inp=open('test_input.txt'))
main()


l = int(input())
a = [int(x) for x in input().strip().split()]
b = [int(x) for x in input().strip().split()]
a.sort()
b.sort()
pa = 0
pb = 0
result = 0
while pa < l and pb < l:
	if a[pa] == b[pb]:
		result += 1
		pa += 1
		pb += 1
	elif a[pa] > b[pb]:
		pb += 1
	else:
		pa += 1
if result == l:
	print(result - 1)
else:
	print(result + 1)


from collections import Counter
(n, a, b) = (int(input()), Counter(map(int, input().split())), Counter(map(int, input().split())))
print(n - 1 if a == b else sum((min(a[i], b[i]) for i in range(1, 1001))) + 1)


import sys

def beautiful_pairs(A, B, n):
	B_t = tuple(B)
	for elem in B_t:
		if elem in A:
			A.remove(elem)
	if len(A) == 0:
		return n - 1
	else:
		return len(B_t) - len(A) + 1
n = int(sys.stdin.readline().strip())
A = list(map(int, sys.stdin.readline().split()))
B = list(map(int, sys.stdin.readline().split()))
print(beautiful_pairs(A, B, n))


N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
A_f = [(i, A[i]) for i in range(len(A))]
B_f = [(i, B[i]) for i in range(len(B))]
A = sorted(A_f, key=lambda x: x[1])
B = sorted(B_f, key=lambda x: x[1])
count = 0
j = 0
i = 0
while i < N and j < N:
	if A[i][1] == B[j][1]:
		count = count + 1
		i = i + 1
		j = j + 1
	elif A[i][1] < B[j][1]:
		i = i + 1
	else:
		j = j + 1
if count != N:
	print(count + 1)
else:
	print(count - 1)


import sys
__author__ = 'alessandro'

def get_max_pairwise_disjoint_beautiful_pairs(n, a, b):
	a_d = {}
	for e in a:
		if e in a_d:
			a_d[e] += 1
		else:
			a_d[e] = 1
	b_remaining = []
	for e in b:
		if e in a_d and a_d[e] > 0:
			a_d[e] -= 1
		else:
			b_remaining.append(e)
	return n - len(b_remaining) + 1 if b_remaining else n - 1

def main(argv):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	print(get_max_pairwise_disjoint_beautiful_pairs(n, a, b))
main(sys.argv)


n = int(input())
x = sorted(list(map(int, input().split())))
y = sorted(list(map(int, input().split())))
t = [i for i in x]
count = 0
for i in t:
	if i in x and i in y:
		x.remove(i)
		y.remove(i)
		count += 1
if len(x) > 0 and len(y) > 0:
	print(count + 1)
else:
	print(count - 1)


from collections import Counter

def pairwise_beautiful(a, b):
	a = sorted(a)
	b = sorted(b)
	a_count = Counter(a)
	b_count = Counter(b)
	counter = 0
	other = False
	for i in a_count.keys():
		a_val = a_count[i]
		b_val = b_count[i]
		if b_val == 0:
			if not other:
				other = True
				counter += 1
		if a_val <= b_val:
			counter += a_val
		else:
			counter += b_val
	if not other:
		counter -= 1
	return counter
n = int(input().strip())
a = [int(i) for i in input().strip().split(' ')]
b = [int(i) for i in input().strip().split(' ')]
print(pairwise_beautiful(a, b))


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.sort()
b.sort()
if a == b:
	print(n - 1)
else:
	count = 0
	(i, j) = (0, 0)
	while i < n and j < n:
		if a[i] == b[j]:
			i += 1
			j += 1
			count += 1
		elif a[i] < b[j]:
			i += 1
		else:
			j += 1
	print(count + 1)


t = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
x = list(a)
y = list(b)
count = 0
for i in x:
	if i in y:
		ind = y.index(i)
		y.pop(ind)
		count += 1
if len(y) != 0:
	print(count + 1)
else:
	print(count - 1)


t = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
x = list(a)
y = list(b)
count = 0
for i in x:
	if i in y:
		ind = y.index(i)
		y.pop(ind)
		count += 1
if len(y) != 0:
	print(count + 1)
else:
	print(count - 1)


import sys
from collections import defaultdict
N = int(input())
A = [int(x) for x in input().strip().split()]
B = [int(x) for x in input().strip().split()]
A.sort()
B.sort()
Adict = defaultdict(int)
Bdict = defaultdict(int)
for x in A:
	Adict[x] += 1
for x in B:
	Bdict[x] += 1
matches = 0
for (k, Av) in Adict.items():
	both = min(Av, Bdict[k])
	matches += both
	Adict[k] -= both
	Bdict[k] -= both
if matches < len(A):
	print(matches + 1)
elif matches == len(A):
	print(matches - 1)


N = int(input())
A = []
B = []
A.extend(input().split())
B.extend(input().split())
for i in range(N):
	A[i] = int(A[i])
	B[i] = int(B[i])
count = 0
ai = 0
bi = 0
A.sort()
B.sort()
while ai < N and bi < N:
	if A[ai] == B[bi]:
		count += 1
		ai += 1
		bi += 1
	elif A[ai] < B[bi]:
		ai += 1
	else:
		bi += 1
if count < N:
	count += 1
else:
	count -= 1
print(count)


from collections import defaultdict

def beautiful_pairs(A, B):
	ele_to_ind_A = defaultdict(list)
	for (i, a) in enumerate(A):
		ele_to_ind_A[a].append(i)
	num_pair = 0
	for b in B:
		if ele_to_ind_A.get(b, []):
			ele_to_ind_A[b].pop()
			num_pair += 1
	if num_pair == len(A):
		return num_pair - 1
	return num_pair + 1
N = int(input())
A = [int(a) for a in input().split(' ')]
B = [int(b) for b in input().split(' ')]
print(beautiful_pairs(A, B))


input()
a = list(sorted((int(x) for x in input().split())))
b = list(sorted((int(x) for x in input().split())))
matching = 0
(i, j) = (0, 0)
while i < len(a) and j < len(b):
	if a[i] < b[j]:
		i += 1
	elif a[i] > b[j]:
		j += 1
	else:
		matching += 1
		i += 1
		j += 1
if matching == len(a):
	print(matching - 1)
else:
	print(matching + 1)


n = int(input())
a = dict()
for x in input().split():
	a[x] = a.get(x, 0) + 1
pairs = 0
for x in input().split():
	if x in a and a[x]:
		a[x] = a[x] - 1
		pairs += 1
if not sum(a.values()):
	pairs += -1
else:
	pairs += 1
print(pairs)


n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
dic = dict()
dic_count = 0
for i in A:
	dic_count += 1
	if i in dic:
		dic[i] += 1
	else:
		dic[i] = 1
for i in B:
	if i in dic and dic[i] != 0:
		dic[i] -= 1
		dic_count -= 1
if dic_count == 0:
	print(len(A) - 1)
else:
	print(len(A) - dic_count + 1)


n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
ans = 0
for x in A:
	try:
		B.remove(x)
		ans += 1
	except ValueError:
		pass
if ans < len(A):
	ans += 1
else:
	ans -= 1
print(ans)


n = int(input())
a = [int(num) for num in input().split(' ')]
b = {}
total = 0
for num in input().split(' '):
	num = int(num)
	b[num] = b.get(num, 0) + 1
for num in a:
	if b.get(num, 0) > 0:
		b[num] -= 1
		total += 1
if total == len(a):
	print(total - 1)
else:
	print(total + 1)


def beaut():
	for k1 in range(T):
		D[A[k1]] = D.get(A[k1], 0) + 1
		D[B[k1]] = D.get(B[k1], 0) - 1
	(min_node, min_value) = (None, 0)
	(max_node, max_value) = (None, 0)
	for _ in D:
		if min_node == None:
			min_node = _
			min_value = D[_]
		if max_node == None:
			max_node = _
			max_value = D[_]
		if D[_] < min_value:
			min_node = _
			min_value = D[_]
		if D[_] > max_value:
			max_node = _
			max_value = D[_]
	if min_node == max_node:
		B.remove(min_node)
		B.append(max_node + 1)
	else:
		B.remove(min_node)
		B.append(max_node)
T = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
L = []
D = {}
beaut()
for k1 in range(T):
	for k2 in range(T):
		if A[k1] == B[k2]:
			L.append([k1, k2])
f = 0
Di = {}
Dj = {}
for _ in L:
	if Di.get(_[0], False) == False and Dj.get(_[1], False) == False:
		Di[_[0]] = True
		Dj[_[1]] = True
		f += 1
print(f)


from collections import Counter
n = int(input())
a = Counter()
for y in [int(x) for x in input().split(' ')]:
	a[y] += 1
b = Counter()
for y in [int(x) for x in input().split(' ')]:
	b[y] += 1
matches = 0
for x in b:
	if a[x] > 0:
		nmatch = min(a[x], b[x])
		a[x] -= nmatch
		b[x] -= nmatch
		matches += nmatch
b = b - Counter()
if not b:
	print(matches - 1)
else:
	print(matches + 1)


n = int(input())
a = [int(x) for x in input().strip().split()]
b = [int(x) for x in input().strip().split()]
x_map = {}
for i in range(n):
	if not a[i] in x_map:
		x_map[a[i]] = [0, 0]
	if not b[i] in x_map:
		x_map[b[i]] = [0, 0]
	x_map[a[i]][0] += 1
	x_map[b[i]][1] += 1
paircount = 0
for key in x_map:
	pair = x_map[key]
	paircount += min(pair)
if n - paircount > 0:
	paircount += 1
else:
	paircount -= 1
print(paircount)


n = int(input())
A = list(map(lambda x: int(x), input().split(' ')))
B = list(map(lambda x: int(x), input().split(' ')))
org_B = len(B)
for a in A:
	if a in B:
		B.remove(a)
if len(A) == 1:
	print(0)
elif len(B) == 0:
	print(org_B - 1)
else:
	print(org_B - len(B) + 1)


n = int(input())
a = list(sorted(map(int, input().split())))
b = list(sorted(map(int, input().split())))
cnt = 0
j = 0
for i in range(n):
	while j < n and b[j] < a[i]:
		j += 1
	if j == n:
		break
	if b[j] == a[i]:
		cnt += 1
		j += 1
print(cnt + 1 if cnt < n else cnt - 1)


n = int(input())
A = sorted([int(i) for i in input().strip().split()])
B = sorted([int(i) for i in input().strip().split()])
i = j = k = 0
while i < n and j < n:
	if A[i] == B[j]:
		k += 1
		i += 1
		j += 1
	elif A[i] < B[j]:
		i += 1
	else:
		j += 1
if k < n:
	print(k + 1)
else:
	print(k - 1)


from collections import Counter
N = int(input().strip())
A = [int(i) for i in input().strip().split()]
B = [int(i) for i in input().strip().split()]
a_count = Counter(A)
b_count = Counter(B)
a_excess = 0
b_excess = 0
a_not_in_b = 0
b_not_in_a = 0
pair_counts = 0
examined_nums = set()
for (k, v) in a_count.items():
	if k in b_count:
		pair_counts += min(a_count[k], b_count[k])
		if a_count[k] < b_count[k]:
			b_excess += 1
		elif a_count[k] > b_count[k]:
			a_excess += 1
	else:
		a_not_in_b += 1
	examined_nums.add(k)
for (k, v) in b_count.items():
	if k not in examined_nums:
		b_not_in_a += 1
if a_not_in_b > 0 and b_not_in_a > 0:
	print(pair_counts + 1)
elif b_not_in_a > 0 and a_excess > 0 or (a_not_in_b > 0 and b_excess > 0):
	print(pair_counts + 1)
else:
	print(pair_counts - 1)


def get_occurences(A):
	a_occurences = {}
	for a in A:
		if not a in a_occurences:
			a_occurences[a] = 1
		else:
			a_occurences[a] += 1
	return a_occurences

def read():
	n = int(input())
	A = map(int, input().split(' '))
	B = map(int, input().split(' '))
	a = get_occurences(A)
	b = get_occurences(B)
	union = set(a).union(set(b))
	diff = False
	c = 0
	for k in union:
		if not k in b:
			b[k] = 0
		if not k in a:
			a[k] = 0
		c += min(a[k], b[k])
		if a[k] != b[k]:
			diff = True
	if not diff:
		print(c - 1)
	elif diff:
		print(c + 1)
	else:
		print(c)
read()


from collections import Counter
trash = input()
A = Counter(input().split())
B = Counter(input().split())
count = 0
for a in A:
	if B[a] > 0:
		c = min(B[a], A[a])
		count += c
		B[a] -= c
		A[a] -= c
notmodified = True
for a in A:
	aiszero = True
	if A[a] != 0 and notmodified:
		count += 1
		notmodified = False
		aiszero = False
		break
for b in B:
	biszero = True
	if B[b] != 0 and notmodified:
		count += 1
		notmodified = False
		biszero = False
		break
if biszero and aiszero:
	count -= 1
print(count)


size = int(input())
a = [int(x) for x in input().split(' ')]
b = [int(x) for x in input().split(' ')]
a_store = {}
b_store = {}
for i in range(size):
	if a[i] in a_store:
		a_store[a[i]].add(i)
	else:
		a_store[a[i]] = {i}
total = 0
for i in range(size):
	if b[i] in a_store:
		if len(a_store[b[i]]) > 0:
			a_store[b[i]].pop()
			total += 1
		if len(a_store[b[i]]) == 0:
			del a_store[b[i]]
if len(a_store) > 0:
	print(total + 1)
else:
	print(total - 1)


N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
dict_a = dict()
common = 0
for x in A:
	if x in dict_a:
		dict_a[x] += 1
	else:
		dict_a[x] = 1
for x in B:
	if dict_a.get(x, False):
		dict_a[x] -= 1
		common += 1
		if dict_a[x] == 0:
			del dict_a[x]
if common == len(B):
	print(common - 1)
else:
	print(common + 1)


from collections import Counter
n = int(input())
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
ca = Counter(a)
cb = Counter(b)
sol = 0
for i in ca.keys():
	x = min(ca[i], cb[i])
	sol += x
	ca[i] -= x
	cb[i] -= x
for i in cb.values():
	if i != 0:
		sol += 1
		break
else:
	if sol == n:
		sol -= 1
print(sol)


from collections import defaultdict
N = int(input().strip())
a = [int(item) for item in input().strip().split()]
b = [int(item) for item in input().strip().split()]
mapA = defaultdict(int)
mapB = defaultdict(int)
for item in a:
	mapA[item] += 1
for item in b:
	mapB[item] += 1
totalPairs = 0
for item in mapA.keys():
	totalPairs += min([mapA[item], mapB[item]])
if totalPairs < N:
	totalPairs += 1
else:
	totalPairs -= 1
print(totalPairs)


n = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
i = 0
j = 0
count_bp = 0
while i < n and j < n:
	if A[i] == B[j]:
		count_bp += 1
		i += 1
		j += 1
	elif A[i] < B[j]:
		i += 1
	else:
		j += 1
if count_bp != n:
	print(count_bp + 1)
else:
	print(count_bp - 1)


def solve(N, A, B):
	(dA, dB) = ({}, {})
	for a in A:
		dA[a] = dA.get(a, 0) + 1
	for b in B:
		dB[b] = dB.get(b, 0) + 1
	(count, c2) = (0, 0)
	for e in set(dA) | set(dB):
		(a, b) = (dA.get(e, 0), dB.get(e, 0))
		count += min(a, b)
		if a != b:
			c2 += 1
	return count + (1 if c2 > 0 else -1)
N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
print(solve(N, A, B))


import sys
from collections import Counter
n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
b = list(map(int, sys.stdin.readline().split()))
aCounter = Counter()
bCounter = Counter()
for i in a:
	aCounter[i] += 1
for i in b:
	bCounter[i] += 1
if len(aCounter) == len(bCounter) and len(aCounter) == 1:
	print(0)
else:
	hasLeftExtra = False
	for i in bCounter.keys():
		if bCounter[i] > aCounter[i]:
			hasLeftExtra = True
			break
	cnt = 0
	hasRightExtra = False
	for i in aCounter.keys():
		cnt += min(aCounter[i], bCounter[i])
		if aCounter[i] > bCounter[i]:
			hasRightExtra = True
	if hasLeftExtra:
		if hasRightExtra:
			cnt += 1
		else:
			pass
	elif not hasRightExtra:
		cnt -= 1
	else:
		pass
	print(cnt)


from collections import Counter

class Solution:

	def __init__(self, a, b):
		self.a = a
		self.b = b

	def solve(self):
		c = Counter(self.a) - Counter(self.b)
		if len(c) == 0:
			return len(a) - 1
		return len(a) - sum((c[x] for x in c)) + 1
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
print(Solution(a, b).solve())


input()
a1 = map(int, input().split())
a2 = map(int, input().split())
f1 = {}
f2 = {}
for x in a1:
	if x in f1:
		f1[x] += 1
	else:
		f1[x] = 1
for x in a2:
	if x in f2:
		f2[x] += 1
	else:
		f2[x] = 1
max_pair = 0
flip = []
for x in f1:
	if x in f2:
		max_pair += min(f1[x], f2[x])
		if f1[x] != f2[x]:
			flip.append(x)
	else:
		flip.append(x)
if flip == []:
	print(max_pair - 1)
else:
	print(max_pair + 1)


from collections import Counter

def ints():
	return [int(X) for X in input().split(' ')]
N = int(input())
A = ints()
B = ints()
a = Counter(A)
b = Counter(B)
common = a & b
common_count = sum(common.values())
just_in_b = b - a
if just_in_b:
	print(common_count + 1)
else:
	print(common_count - 1)


N = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
M = max(max(A), max(B)) + 1
Ac = [[] for i in range(M)]
Bc = [[] for i in range(M)]
for i in range(N):
	Ac[A[i]] += [i]
	Bc[B[i]] += [i]
best = 0
for i in range(M):
	if Ac[i] and Bc[i]:
		best += max(len(Ac[i]), len(Bc[i])) - abs(len(Ac[i]) - len(Bc[i]))
if best == N:
	print(best - 1)
else:
	print(best + 1)


n = int(input().strip())
counter = dict()
for a in [int(x) for x in input().strip().split()]:
	if a not in counter:
		counter[a] = 0
	counter[a] += 1
bp = 0
unpaired = False
for b in [int(x) for x in input().strip().split()]:
	if b in counter and counter[b] > 0:
		counter[b] -= 1
		bp += 1
	else:
		unpaired = True
if unpaired:
	print(bp + 1)
else:
	print(bp - 1)


from collections import Counter
n = int(input())
p1 = [int(x) for x in input().split()]
p2 = [int(x) for x in input().split()]
(d1, d2) = (Counter(), Counter())
for x in p1:
	d1[x] += 1
for x in p2:
	d2[x] += 1
ans = 0
for x in d1:
	ans += min(d1[x], d2[x])
if ans == n:
	ans -= 1
else:
	ans += 1
print(ans)


input()
a = input().strip().split()
b = input().strip().split()
count = 0
for el in a[:]:
	if el in b:
		a.remove(el)
		b.remove(el)
		count += 1
print(count + {1: 1, 0: -1}[bool(len(b))])


import re
import collections
n = int(input())
A = re.split('\\s+', input().strip())
B = re.split('\\s+', input().strip())
Ac = collections.Counter(A)
Bc = collections.Counter(B)
pairs = sum([c for (x, c) in (Ac & Bc).items()])
if pairs < n:
	print(pairs + 1)
else:
	print(n - 1)


def read_input():
	size = int(input())
	array1 = get_int_list(input())
	array2 = get_int_list(input())
	return (size, array1, array2)

class BeautifulPairs:

	def __init__(self):
		(self.size, self.array1, self.array2) = read_input()
		self.array1.sort()
		self.array2.sort()

	def calculate(self):
		pairs = 0
		left_over1 = 0
		left_over2 = 0
		pointer1 = 0
		pointer2 = 0
		while pointer1 < self.size and pointer2 < self.size:
			if self.array1[pointer1] == self.array2[pointer2]:
				pairs += 1
				pointer1 += 1
				pointer2 += 1
			elif self.array1[pointer1] < self.array2[pointer2]:
				left_over1 += 1
				pointer1 += 1
			else:
				left_over2 += 1
				pointer2 += 1
		if pointer1 < self.size:
			left_over1 += 1
		if pointer2 < self.size:
			left_over2 += 1
		if left_over1 > 0 and left_over2 > 0:
			pairs += 1
		else:
			pairs -= 1
		return pairs

def main():
	my_object = BeautifulPairs()
	print(my_object.calculate())

def get_int_list(in_str):
	return [int(i) for i in in_str.strip().split()]
main()


def get_disjoint(pairs):
	xs = set()
	ys = set()
	result = []
	for (i, j) in pairs:
		if i not in xs and j not in ys:
			result.append((i, j))
			xs.add(i)
			ys.add(j)
	return (result, xs, ys)

def get_beautiful_pairs(a, b):
	result = []
	for ai in range(len(a)):
		for bi in range(len(b)):
			if a[ai] == b[bi]:
				result.append((ai, bi))
	return result
n = int(input())
a = [int(x) for x in input().split(' ')]
b = [int(x) for x in input().split(' ')]
(initial_disjoint, xs, ys) = get_disjoint(get_beautiful_pairs(a, b))
not_used_ai = next(filter(lambda x: x not in xs, range(len(a))), None)
not_used_bi = next(filter(lambda x: x not in ys, range(len(b))), None)
if not_used_ai is None and not_used_bi is None:
	print(len(initial_disjoint) - 1)
else:
	b[not_used_bi] = a[not_used_ai]
	(disjoint, _, _) = get_disjoint(get_beautiful_pairs(a, b))
	print(len(disjoint))


from collections import Counter
N = int(input())
A = Counter(list(map(int, input().split())))
B = Counter(list(map(int, input().split())))
count = 0
for a in A.keys():
	count += min(A[a], B[a])
if count == sum(A.values()):
	print(count - 1)
else:
	print(count + 1)


import sys
n = int(input())
arr1 = [int(x) for x in input().strip().split(' ')]
arr2 = [int(x) for x in input().strip().split(' ')]
itharr = []
jtharr = []
for i in range(n):
	for j in range(n):
		if arr1[i] == arr2[j]:
			if i not in itharr and j not in jtharr:
				itharr.append(i)
				jtharr.append(j)
if len(itharr) < len(arr1):
	print(len(itharr) + 1)
else:
	print(len(itharr) - 1)


N = int(input())
A = sorted([int(x) for x in input().split()])
B = sorted([int(x) for x in input().split()])
matched = 0
unmatched = 0
while A and B:
	if A[0] == B[0]:
		A.pop(0)
		B.pop(0)
		matched += 1
	elif A[0] < B[0]:
		A.pop(0)
		unmatched += 1
	else:
		B.pop(0)
		unmatched += 1
if unmatched == 0:
	matched -= 1
else:
	matched += 1
print(matched)


N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
count = 0
for i in range(N):
	for j in range(N):
		if A[i] == B[j]:
			count += 1
			A[i] = float('inf')
			B[j] = float('inf')
			break
flag = False
for i in range(N):
	if A[i] != float('inf'):
		flag = True
if flag:
	count += 1
else:
	count -= 1
print(count)


import collections
import functools
N = int(input())
A = list(map(int, input().split(' ')))
B = list(map(int, input().split(' ')))
table = collections.Counter(B) - collections.Counter(A)
tally = 0 if len(table) == 0 else functools.reduce(lambda x, y: x + y, table.values())
print(len(B) - 1 if tally == 0 else len(B) - tally + 1)


N = int(input())
A = [int(i) for i in input().strip().split()]
B = [int(i) for i in input().strip().split()]
num = 0
for a in A:
	if a in B:
		num += 1
		B.remove(a)
if num == N:
	print(num - 1)
else:
	print(num + 1)


from collections import Counter
n = int(input())
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
c_a = Counter(a)
c_b = Counter(b)
result = 0
incr = False
decr = False
for key in set(list(c_a) + list(c_b)):
	result += min(c_a[key], c_b[key])
	if c_a[key] > c_b[key]:
		incr = True
	elif c_b[key] > c_a[key]:
		decr = True
if incr and decr:
	result += 1
elif not incr and (not decr):
	result -= 1
print(result)


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
cnt = 0
for k in a:
	if k in b:
		cnt += 1
		b[b.index(k)] = 1001
if cnt != n:
	print(cnt + 1)
else:
	print(cnt - 1)


n = int(input())
arr1 = input().strip().split(' ')
arr2 = input().strip().split(' ')
count = 0
for i in range(n):
	for j in arr2:
		if arr1[i] == j:
			arr2.remove(j)
			count += 1
			break
if len(arr1) == count:
	print(count - 1)
else:
	print(count + 1)


from collections import Counter
input()
(l1, l2) = [Counter(input().split()) for i in range(2)]
hasOff = False
total = 0
for i in l1:
	if l1[i] != l2[i]:
		hasOff = True
		total += min(l1[i], l2[i])
	else:
		total += l1[i]
if hasOff:
	total += 1
else:
	total -= 1
print(total)


n = int(input())
a = input().split(' ')
b = input().split(' ')
dic = {}
for i in range(n):
	if a[i] in dic:
		dic[a[i]].append(i)
	else:
		dic[a[i]] = [i]
count = 0
for j in range(n):
	if b[j] in dic:
		if len(dic[b[j]]) > 0:
			dic[b[j]].pop()
			count += 1
			if len(dic[b[j]]) == 0:
				del dic[b[j]]
		else:
			del dic[b[j]]
if len(dic) == 0:
	count -= 1
else:
	count += 1
print(count)


from collections import deque
n = int(input())
A = deque(sorted(map(int, input().split())))
B = deque(sorted(map(int, input().split())))
sA = deque()
sB = deque()
c = 0
while A and B:
	if A[0] < B[0]:
		sA += (A.popleft(),)
	elif B[0] < A[0]:
		sB += (B.popleft(),)
	else:
		A.popleft()
		B.popleft()
		c += 1
print(c + 1 if sA or A else c - 1)


def count(A):
	c = {}
	for x in A:
		c[x] = c.get(x, 0) + 1
	return c
N = int(input())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
Acount = count(A)
Bcount = count(B)
pairs = 0
for (x, c) in Acount.items():
	pairs += min(c, Bcount.get(x, 0))
if pairs == N:
	print(pairs - 1)
else:
	print(pairs + 1)


n = int(input().strip())
a1 = [int(i) for i in input().strip().split(' ')]
a2 = [int(i) for i in input().strip().split(' ')]
a1.sort()
a2.sort()
f2 = 0
i = 0
j = 0
c = 0
while i < n and j < n:
	while j < n and a1[i] > a2[j]:
		f2 = 1
		j = j + 1
	if j == n:
		break
	if a1[i] == a2[j]:
		c += 1
		j = j + 1
	elif a1[i] < a2[j]:
		f2 = 1
	i += 1
if f2 == 1:
	c = c + 1
if f2 == 0:
	c = c - 1
print(c)


n = int(input())
counter = {}
for num in map(int, input().split()):
	if num in counter:
		counter[num] += 1
	else:
		counter[num] = 1
for num in map(int, input().split()):
	if num in counter:
		counter[num] -= 1
	else:
		counter[num] = -1
diff = sum(map(abs, counter.values())) // 2
if diff != 0:
	diff -= 1
else:
	diff += 1
print(n - diff)


n = int(input())
a = [int(x) for x in input().split(' ')]
b = [int(x) for x in input().split(' ')]
from collections import Counter
a_count = Counter(a)
b_count = Counter(b)
bkeys = b_count.keys()
diff = 0
ans = 0
for a_key in a_count.keys():
	if a_key in bkeys:
		flag = True
		ans += min(a_count[a_key], b_count[a_key])
		diff += abs(a_count[a_key] - b_count[a_key])
	else:
		diff += 1
if diff == 0:
	print(ans - 1)
else:
	print(ans + 1)


import sys

def buildDictionary(A, B):
	dA = dict()
	A1 = A.copy()
	setA = list(set(A))
	for i in range(len(setA)):
		dA[setA[i]] = list()
	dB = dict()
	B1 = A.copy()
	setB = list(set(B))
	for i in range(len(setB)):
		dB[setB[i]] = list()
	for i in range(N):
		dA[A[i]].append(i)
		dB[B[i]].append(i)
	return [dA, dB]

def countPairs(dA, dB):
	dAc = dA.copy()
	dBc = dB.copy()
	setA = list(set(A))
	total = 0
	for i in range(len(setA)):
		elt = setA[i]
		appA = dAc[elt]
		if elt in dBc:
			appB = dBc[elt]
		else:
			appB = list()
		if len(appA) == len(appB):
			dAc[elt] = list()
			dBc[elt] = list()
			total += len(appA)
		elif len(appA) > len(appB):
			dBc[elt] = list()
			del dAc[elt][:len(B)]
			total += len(appB)
		else:
			dAc[elt] = list()
			del dBc[elt][:len(A)]
			total += len(appA)
	return total
N = int(input().strip())
A = [int(q_temp) for q_temp in input().strip().split(' ')]
B = [int(q_temp) for q_temp in input().strip().split(' ')]
sA = A.copy()
sA.sort()
sB = B.copy()
sB.sort()
if sA == sB:
	print(len(A) - 1)
else:
	[dA, dB] = buildDictionary(A, B)
	total = countPairs(dA, dB)
	print(total + 1)


n = input()
nums = input()
a = nums.split(' ')
nums = input()
b = nums.split(' ')
a1 = []
b1 = []
for i in a:
	a1.append(int(i))
for i in b:
	b1.append(int(i))
ex = []
cnt = 0
for i in a1:
	if i in b1:
		b1.remove(i)
		cnt += 1
	else:
		ex.append(i)
if len(ex) > 0:
	print(cnt + 1)
else:
	print(cnt - 1)


n = int(input())
A = [int(i) for i in input().split()]
B = [int(i) for i in input().split()]
countA = [0 for i in range(1001)]
countB = [0 for i in range(1001)]
for i in range(n):
	countA[A[i]] += 1
	countB[B[i]] += 1
pairs = 0
haveextra = False
for i in range(1001):
	pairs += min(countA[i], countB[i])
	if countA[i] > countB[i]:
		haveextra = True
if haveextra:
	print(pairs + 1)
elif countA == countB:
	print(pairs - 1)
else:
	print(pairs)


n = int(input())
d = {}
for i in map(int, input().split()):
	d[i] = 1 + d.get(i, 0)
a = 0
for j in map(int, input().split()):
	if j in d:
		a += 1
		d[j] -= 1
		if d[j] == 0:
			del d[j]
print(a + (1 if d else -1))


from collections import Counter

def int_tokenize(line):
	return [int(token) for token in line.strip().split()]
n = int(input().strip())
a = int_tokenize(input())
b = int_tokenize(input())
a_counts = Counter(a)
b_counts = Counter(b)
nums = set(a_counts.keys()) | set(b_counts.keys())
max_diff = -float('inf')
min_diff = float('inf')
max_num = None
min_num = None
for num in nums:
	diff = a_counts[num] - b_counts[num]
	if diff > max_diff:
		max_diff = diff
		max_num = num
	if diff < min_diff:
		min_diff = diff
		min_num = num
b_counts[min_num] -= 1
b_counts[max_num] += 1
total = 0
for num in a_counts:
	total += min(a_counts[num], b_counts[num])
if min_num == max_num:
	total -= 1
print(total)


N = int(input().strip())
A = [int(i) for i in input().strip().split(' ')]
B = [int(i) for i in input().strip().split(' ')]
count = 0
for i in range(len(A)):
	for j in range(len(B)):
		if A[i] == B[j]:
			del B[j]
			count += 1
			break
	continue
if len(B) > 0:
	count += 1
else:
	count -= 1
print(count)


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
A = {i: [] for i in range(n)}
B = {i: [] for i in range(n)}
for i in range(n):
	for j in range(n):
		if a[i] == b[j]:
			A[i].append(j)
			B[j].append(i)
prohibited = {'A': [], 'B': []}
for v in range(n):
	for u in A[v]:
		if not u in prohibited['B']:
			prohibited['A'].append(v)
			prohibited['B'].append(u)
			break
if len(prohibited['B']) < n:
	print(len(prohibited['B']) + 1)
else:
	print(n - 1)


n = int(input())
a = [int(x) for x in input().split(' ')]
b = [int(x) for x in input().split(' ')]
bleft = []
rtn = 0
for x in b:
	if x in a:
		a[a.index(x)] = None
		rtn += 1
print(rtn + 1 if rtn < n else n - 1)


N = int(input())
A = [int(x) for x in input().split(' ')]
B = [int(x) for x in input().split(' ')]
D = dict([])
for a in A:
	try:
		D[a] += 1
	except:
		D[a] = 1
l = 0
for b in B:
	try:
		if D[b] > 0:
			D[b] -= 1
			l += 1
	except:
		l = l
if l < N:
	print(repr(l + 1))
else:
	print(repr(N - 1))


n = int(input())
arr = list(map(int, input().split()))
brr = list(map(int, input().split()))
di = dict()
for i in arr:
	if i in di:
		di[i] += 1
	else:
		di[i] = 1
c = 0
for i in brr:
	if i in di and di[i] > 0:
		di[i] -= 1
		c += 1
if c != n:
	print(c + 1)
else:
	print(c - 1)


def find(a, b, N, counter):
	counter = 0
	for item1 in b[:]:
		for item2 in a[:]:
			if item1 == item2:
				counter = counter + 1
				a.remove(item1)
				b.remove(item2)
				break
	if not a:
		return counter - 1
	else:
		return counter + 1

def main():
	N = int(input())
	s = input()
	a = [int(i) for i in s.split(' ')]
	s = input()
	b = [int(i) for i in s.split(' ')]
	counter = 0
	print(find(a, b, N, counter))
main()


from collections import Counter
n = range(int(input()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ac = Counter(a)
bc = Counter(b)
if ac - bc and bc - ac:
	b[b.index(list(bc - ac)[0])] = list(ac - bc)[0]
else:
	b[0] = 0
bc = Counter(b)
print(sum((bc - (bc - ac)).values()))


def beautifulpairs():
	input()
	A = sorted([int(x) for x in input().split(' ')])
	B = sorted([int(x) for x in input().split(' ')])
	(i, j) = (0, 0)
	pairs = 0
	extra = 0
	while i < len(A) and j < len(A):
		if A[i] == B[j]:
			pairs += 1
			i += 1
			j += 1
		elif A[i] < B[j]:
			i += 1
			extra = 1
		else:
			j += 1
			extra = 1
	pairs = min(len(A) - 1, pairs)
	print(pairs + extra)
	return pairs + extra
beautifulpairs()


n = int(input().strip())
a = list(map(int, input().strip().split()))
b = list(map(int, input().strip().split()))
counter = {x: 0 for x in a}
for i in a:
	counter[i] += 1
count = 0
for i in b:
	if counter.get(i) and counter[i] > 0:
		counter[i] -= 1
		count += 1
if count == n:
	print(count - 1)
else:
	print(count + 1)


import math
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
da = {}
db = {}
ask = []
cost = 0
for i in a:
	if i in da:
		da[i] += 1
	else:
		da[i] = 1
		ask.append(i)
for j in b:
	if j in db:
		db[j] += 1
	else:
		db[j] = 1
for k in da:
	if k in db:
		cost += min(da[k], db[k])
if cost == n:
	cost -= 1
else:
	cost += 1
print(cost)


k = int(input())
a = list(map(lambda x: int(x), input().split()))
b = list(map(lambda x: int(x), input().split()))
c = 0
for i in a:
	if i in b:
		i = b.index(i)
		b[i] = False
		c += 1
if c == len(a):
	c -= 1
elif c < len(a):
	c += 1
print(c)


n = int(input().strip())
a = [int(n) for n in input().strip().split(' ')]
b = [int(n) for n in input().strip().split(' ')]
a.sort()
b.sort()
(i, j, count) = (0, 0, 0)
while i < n and j < n:
	if a[i] == b[j]:
		count += 1
		j += 1
		i += 1
	elif a[i] > b[j]:
		j += 1
	elif a[i] < b[j]:
		i += 1
if count == n:
	print(n - 1)
else:
	print(count + 1)


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.sort()
b.sort()
i = 0
j = 0
c = 0
while not i == n and (not j == n):
	if a[i] == b[j]:
		c += 1
		i += 1
		j += 1
	elif a[i] < b[j]:
		i += 1
	else:
		j += 1
if not c == n:
	print(c + 1)
else:
	print(c - 1)


from collections import Counter
n = int(input())
a = Counter([int(x) for x in input().split()])
b = Counter([int(x) for x in input().split()])
pairs = 0
for i in a:
	if i in b:
		pairs += min(a[i], b[i])
if pairs < n:
	pairs += 1
else:
	pairs -= 1
print(pairs)


N = int(input())
A = [int(item) for item in input().split()]
B = [int(item) for item in input().split()]
i = 0
count = 0
flag = 0
j = 0
M = N
while i < N:
	while j < M:
		if A[i] == B[j]:
			count += 1
			B.pop(j)
			M -= 1
			j = 0
			break
		else:
			j += 1
	i += 1
	j = 0
if count == N:
	print(count - 1)
else:
	print(count + 1)


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
d = {}
for elem in a:
	if elem in d:
		d[elem] += 1
	else:
		d[elem] = 1
ans = 0
for elem in b:
	if elem in d and d[elem] > 0:
		d[elem] -= 1
		ans += 1
if ans == n:
	print(n - 1)
else:
	print(ans + 1)


n = int(input())
arr1 = [int(i) for i in input().split()]
arr2 = [int(i) for i in input().split()]
arrx = [0] * 1001
(pairs, extra) = (0, 0)
for i in arr1:
	arrx[i] += 1
for i in arr2:
	if arrx[i] > 0:
		arrx[i] -= 1
		pairs += 1
	else:
		extra += 1
if extra > 0:
	print(pairs + 1)
else:
	print(pairs - 1)


n = input().strip()
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
a_dict = {}
for num in a:
	if num not in a_dict:
		a_dict[num] = 1
	else:
		a_dict[num] += 1
b_dict = {}
for num in b:
	if num not in b_dict:
		b_dict[num] = 1
	else:
		b_dict[num] += 1
count = 0
for num in b:
	if num in a_dict:
		if a_dict[num] > 0:
			count += 1
			a_dict[num] -= 1
			b_dict[num] -= 1
a_found_unused = False
b_found_unused = False
for (key, value) in a_dict.items():
	if value > 0:
		a_found_unused = True
		break
for (key, value) in b_dict.items():
	if value > 0:
		b_found_unused = True
		break
if a_found_unused or b_found_unused:
	print(count + 1)
else:
	print(count - 1)


n = int(input())
a = list(map(int, input().strip().split()))
b = list(map(int, input().strip().split()))
from collections import defaultdict
tally = defaultdict(int)
for c in a:
	tally[c] += 1
for c in b:
	if c in tally and tally[c] == 1:
		del tally[c]
	else:
		tally[c] -= 1
ugly = sum(map(abs, tally.values())) // 2
if ugly > 0:
	ugly -= 1
else:
	ugly += 1
print(n - ugly)


from collections import defaultdict
c = defaultdict(int)
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
x = 0
for i in a:
	c[i] += 1
for i in b:
	if c[i] > 0:
		c[i] -= 1
		x += 1
if x == n:
	print(x - 1)
else:
	print(x + 1)


n = int(input())
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
res = 0
for i in range(n):
	if a[i] in b:
		res += 1
		del b[b.index(a[i])]
if len(b) > 0:
	res += 1
else:
	res -= 1
print(res)


n = int(input())
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
s = 0
for i in range(n):
	if a[i] in b:
		del b[b.index(a[i])]
		s += 1
if len(b) > 0:
	s += 1
else:
	s -= 1
print(s)


from collections import Counter
n = int(input())
a = Counter((int(x) for x in input().split()))
b = Counter((int(x) for x in input().split()))
r = sum((a & b).values())
print(r + (-1 if r == n else 1))


n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
res = 0
for i in range(n):
	for j in range(n):
		if a[i] == b[j] and a[i] > 0:
			res += 1
			a[i] = 0
			b[j] = 0
if res < n:
	res += 1
else:
	res -= 1
print(res)


n = input().strip().split(' ')
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]
a.sort()
b.sort()
i = j = 0
p = 0
while i < len(a) and j < len(b):
	if i < len(a) and j < len(b) and (a[i] == b[j]):
		p += 1
		i += 1
		j += 1
	elif i < len(a) and a[i] < b[j]:
		i += 1
	elif j < len(b) and b[j] < a[i]:
		j += 1
if p < len(b):
	p += 1
else:
	p -= 1
print(p)


n = int(input())
(a, b) = ([], [])
l = input().strip().split(' ')
l2 = input().strip().split(' ')
for i in range(n):
	a.append(int(l[i]))
	b.append(int(l2[i]))
a.sort()
b.sort()
i = j = total = 0
while i < n and j < n:
	while i < n and j < n and (a[i] < b[j]):
		i += 1
	while j < n and i < n and (b[j] < a[i]):
		j += 1
	if i < n and j < n and (a[i] == b[j]):
		total += 1
		i += 1
		j += 1
print(total + 1 if total != n else total - 1)