Given two Arrays A[] and B[] of length N and M respectively. Find the minimum number of insertions and deletions on the array A[], required to make both the arrays identical.
Note: Array B[] is sorted and all its elements are distinct, operations can be performed at any index not necessarily at end.
 
Example 1:
Input:
N = 5, M = 3
A[] = {1, 2, 5, 3, 1}
B[] = {1, 3, 5}
Output:
4
Explanation:
We need to delete 2 and replace it with 3.
This costs 2 steps. Further, we will have to
delete the last two elements from A to
obtain an identical array to B. Overall, it
results in 4 steps.
Example 2:
Input:
N = 2, M = 2
A[] = {1, 4}
B[] = {1, 4}
Output :
0
Explanation:
Both the Arrays are already identical.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function minInsAndDel() which takes two integers N and M, and two arrays A of size N and B of size M respectively as input and returns the minimum insertions and deletions required.
Expected Time Complexity: O(NlogN)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ A[i], B[i] ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM_HARD
Tags: String algorithms

Dynamic programming

Data structures

Starter code: #User function Template for python3

class Solution:
    def minInsAndDel(self, A, B, N, M):
        # code here 

Solutions:
from bisect import bisect_left

def LongestIncreasingSubsequenceLength(v):
	if len(v) == 0:
		return 0
	tail = [0 for i in range(len(v) + 1)]
	length = 1
	tail[0] = v[0]
	for i in range(1, len(v)):
		if v[i] > tail[length - 1]:
			tail[length] = v[i]
			length += 1
		else:
			tail[bisect_left(tail, v[i], 0, length - 1)] = v[i]
	return length

class Solution:

	def minInsAndDel(self, arr, brr, N, M):
		vec = []
		s = set(brr)
		for i in arr:
			if i in s:
				vec.append(i)
		res = LongestIncreasingSubsequenceLength(vec)
		return abs(N - res) + abs(M - res)


import bisect

class Solution:

	def LISLength(self, v):
		if len(v) == 0:
			return 0
		tail = [0 for i in range(len(v) + 1)]
		length = 1
		tail[0] = v[0]
		for i in range(1, len(v)):
			if v[i] > tail[length - 1]:
				tail[length] = v[i]
				length += 1
			else:
				tail[bisect.bisect_left(tail, v[i], 0, length - 1)] = v[i]
		return length

	def minInsAndDel(self, A, B, N, M):
		mp = dict()
		for i in range(M):
			mp[B[i]] = i
		res = []
		for i in range(N):
			if A[i] in mp:
				res.append(mp[A[i]])
		ans = N - self.LISLength(res) + (M - self.LISLength(res))
		return ans


from bisect import bisect_left

class Solution:

	def minInsAndDel(self, A, B, n, m):
		common = []
		s = set()
		for i in range(0, m):
			s.add(B[i])
		for i in range(0, n):
			if A[i] in s:
				common.append(A[i])
		lis = []
		for e in common:
			it = bisect_left(lis, e, 0, len(lis))
			if it != len(lis):
				lis[it] = e
			else:
				lis.append(e)
		ans = 0
		ans = m - len(lis)
		ans += n - len(lis)
		return ans


from bisect import bisect_left

class Solution:

	def minInsAndDel(self, A, B, N, M):
		up_A = []
		for i in range(N):
			index = bisect_left(B, A[i])
			if index != len(B) and B[index] == A[i]:
				up_A.append(A[i])
		if not up_A:
			return N + M
		stack = [up_A[0]]
		n = len(up_A)
		for i in range(1, n):
			if up_A[i] > stack[-1]:
				stack.append(up_A[i])
			else:
				index = bisect_left(stack, up_A[i])
				stack[index] = up_A[i]
		return N - len(stack) + M - len(stack)


from bisect import bisect_left

def lis(v):
	if len(v) == 0:
		return 0
	l = [v[0]]
	for i in range(1, len(v)):
		if v[i] > l[-1]:
			l.append(v[i])
		else:
			l[bisect_left(l, v[i], 0, len(l) - 1)] = v[i]
	return len(l)

class Solution:

	def minInsAndDel(self, A, B, N, M):
		B2 = set(B)
		A2 = []
		for a in A:
			if a in B2:
				A2.append(a)
		return N + M - 2 * lis(A2)


def ceil(arr, left, right, ele):
	c = -1
	while left <= right:
		mid = (left + right) // 2
		if arr[mid] > ele:
			c = mid
			right = mid - 1
		elif arr[mid] < ele:
			left = mid + 1
		else:
			return mid
	return c

def LIS(arr):
	res = []
	res.append(arr[0])
	for i in range(1, len(arr)):
		if res[-1] < arr[i]:
			res.append(arr[i])
		else:
			k = ceil(res, 0, len(res), arr[i])
			res[k] = arr[i]
	return len(res)

class Solution:

	def minInsAndDel(self, A, B, N, M):
		b_set = {i: 1 for i in B}
		a = []
		for i in A:
			if i in b_set.keys():
				a.append(i)
		if len(a) == 0:
			return N + M
		lis = LIS(a)
		return N + M - 2 * lis


from bisect import *

class Solution:

	def minInsAndDel(self, A, B, N, M):
		subA = []
		sB = set(B)
		for n in A:
			if n in sB:
				subA.append(n)
		l = []
		for n in subA:
			ind = bisect_left(l, n)
			if ind == len(l):
				l.append(n)
			l[ind] = n
		lis = len(l)
		return len(A) - lis + len(B) - lis


def bs(A, key):
	l = 0
	r = len(A) - 1
	ans = r + 1
	while l <= r:
		mid = l + (r - l >> 1)
		if A[mid] > key:
			r = mid - 1
			ans = mid
		elif A[mid] == key:
			return mid
		else:
			l = mid + 1
	return ans

def lis(A):
	N = len(A)
	if N == 0:
		return 0
	dp = [A[0]]
	for i in range(1, N):
		ix = bs(dp, A[i])
		if ix == len(dp):
			dp.append(A[i])
		else:
			dp[ix] = A[i]
	return len(dp)

class Solution:

	def minInsAndDel(self, A, B, N, M):
		mp = {}
		for i in range(M):
			mp[B[i]] = i
		res = []
		for i in range(N):
			if A[i] in mp:
				res.append(mp[A[i]])
		c = lis(res)
		return N - c + M - c


class Solution:

	def minInsAndDel(self, x, y, n, m):

		def binse(e):
			i = 0
			j = len(z) - 1
			ans = j + 1
			while i <= j:
				m = (i + j) // 2
				if z[m] >= e:
					ans = m
					j = m - 1
				else:
					i = m + 1
			return ans
		se = set(y)
		q = []
		for i in range(n):
			if x[i] in se:
				q.append(x[i])
		x = q
		z = []
		nn = n
		n = len(x)
		for i in range(n):
			if not z or z[-1] < x[i]:
				z.append(x[i])
			else:
				z[binse(x[i])] = x[i]
		return m - len(z) + nn - len(z)


class Solution:

	def minInsAndDel(self, a, b, m, n):
		bset = set(b)
		lis = []
		import bisect
		newarr = []
		for i in a:
			if i in bset:
				newarr.append(i)
		counter = 0
		for i in newarr:
			ind = bisect.bisect_left(lis, i)
			if ind == counter:
				lis.append(i)
				counter += 1
			else:
				lis[ind] = i
		return m + n - 2 * counter


from bisect import *

class Solution:

	def minInsAndDel(self, A, B, N, M):

		def lis(arr):
			n = len(arr)
			if n == 0:
				return 0
			t = [0]
			l = 1
			t[0] = arr[0]
			for i in range(1, n):
				if arr[i] > t[l - 1]:
					t.append(arr[i])
					l += 1
				else:
					t[bisect_left(t, arr[i])] = arr[i]
			return l
		s = set()
		for ele in B:
			s.add(ele)
		cnt = 0
		Anew = []
		for ele in A:
			if ele in s:
				Anew += [ele]
			else:
				cnt += 1
		l = lis(Anew)
		return cnt + len(Anew) - l + M - l


from bisect import bisect_left
import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def minInsAndDel(self, A, B, N, M):

		def Longest(v):
			if len(v) == 0:
				return 0
			tail = [0 for i in range(len(v) + 1)]
			length = 1
			tail[0] = v[0]
			for i in range(1, len(v)):
				if v[i] > tail[length - 1]:
					tail[length] = v[i]
					length += 1
				else:
					tail[bisect_left(tail, v[i], 0, length - 1)] = v[i]
			return length
		dicB = {i: 1 for i in B}
		newA = [i for i in A if i in dicB]
		longest = Longest(newA)
		RemInA = N - longest
		RemInB = len(B) - longest
		return RemInA + RemInB


from bisect import bisect_left
import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def minInsAndDel(self, A, B, N, M):

		def LongestIncreasingSubsequenceLength(v):
			if len(v) == 0:
				return 0
			tail = [0 for i in range(len(v) + 1)]
			length = 1
			tail[0] = v[0]
			for i in range(1, len(v)):
				if v[i] > tail[length - 1]:
					tail[length] = v[i]
					length += 1
				else:
					tail[bisect_left(tail, v[i], 0, length - 1)] = v[i]
			return length
		dicB = {i: 1 for i in B}
		newA = [i for i in A if i in dicB]
		longest = LongestIncreasingSubsequenceLength(newA)
		diff1 = N - longest
		diff2 = len(B) - longest
		return diff1 + diff2


import bisect

class Solution:

	def minInsAndDel(self, A, B, N, M):
		arr = []
		b = set(B)
		a = set(A)
		c = 0
		for i in range(len(B)):
			if B[i] not in a:
				c += 1
				b.remove(B[i])
		for i in range(len(A)):
			if A[i] in b:
				arr.append(A[i])
			else:
				c += 1
		if len(arr) > 0:
			lis = [arr[0]]
			for i in range(1, len(arr)):
				if lis[-1] < arr[i]:
					lis.append(arr[i])
				else:
					id = bisect.bisect_left(lis, arr[i])
					lis[id] = arr[i]
			c = c + (len(arr) - len(lis)) + (len(b) - len(lis))
		return c


class Solution:

	def ceil(self, arr, x):
		left = 0
		right = len(arr) - 1
		ans = -1
		while left <= right:
			mid = (left + right) // 2
			if arr[mid] >= x:
				ans = mid
				right = mid - 1
			else:
				left = mid + 1
		return ans

	def minInsAndDel(self, A, B, N, M):
		has = set(B)
		arr = []
		for i in A:
			if i in has:
				arr.append(i)
		res = []
		for i in range(len(arr)):
			if not res:
				res.append(arr[i])
			elif res[-1] < arr[i]:
				res.append(arr[i])
			elif res[0] > arr[i]:
				res[0] = arr[i]
			else:
				res[self.ceil(res, arr[i])] = arr[i]
		return N - len(res) + M - len(res)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, M) = map(int, input().split())
		A = list(map(int, input().split()))
		B = list(map(int, input().split()))
		ob = Solution()
		print(ob.minInsAndDel(A, B, N, M))


from bisect import bisect_left

class Solution:

	def minInsAndDel(self, A, B, N, M):
		B = set(B)
		n = len(A)
		m = len(B)
		A = [i for i in A if i in B]
		st = []
		ans = n - len(A)
		for i in A:
			if not st or i > st[-1]:
				st.append(i)
			else:
				idx = bisect_left(st, i)
				st[idx] = i
		return n + m - 2 * len(st)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, M) = map(int, input().split())
		A = list(map(int, input().split()))
		B = list(map(int, input().split()))
		ob = Solution()
		print(ob.minInsAndDel(A, B, N, M))


class Solution:

	def minInsAndDel(self, A, B, N, M):

		def lower_bound(arr, n, k):
			l = 0
			h = n - 1
			while l < h:
				mid = (l + h) // 2
				if k <= arr[mid]:
					h = mid
				else:
					l = mid + 1
			if l < n and arr[l] < k:
				l += 1
			return l

		def LIS(arr, n):
			if n <= 1:
				return n
			ans = [arr[0]]
			ans_len = 1
			for i in range(1, n):
				if arr[i] > ans[ans_len - 1]:
					ans.append(arr[i])
					ans_len += 1
				else:
					index = lower_bound(ans, ans_len, arr[i])
					ans[index] = arr[i]
			return ans_len
		s = set()
		arr = []
		for i in range(M):
			s.add(B[i])
		for i in range(N):
			if A[i] in s:
				arr.append(A[i])
		lis = LIS(arr, len(arr))
		return N + M - 2 * lis
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, M) = map(int, input().split())
		A = list(map(int, input().split()))
		B = list(map(int, input().split()))
		ob = Solution()
		print(ob.minInsAndDel(A, B, N, M))


import bisect

class Solution:

	def binary(self, y, v, l, r):
		m = (r - l) // 2
		if r == l:
			return l
		if r - l == 1:
			if y[l] >= v:
				return l
			else:
				return r
		if m == 1:
			if y[(r + l) // 2 - 1] >= v:
				return (r + l) // 2 - 1
			elif y[(r + l) // 2] >= v:
				return (r + l) // 2
			else:
				return (r + l) // 2 + 1
		if y[m] > v:
			return self.binary(y, v, l, m - 1)
		elif y[m] == v:
			return m
		else:
			return self.binary(y, v, m + 1, r)

	def minInsAndDel(self, a, b, n, m):
		d = {}
		for i in b:
			d[i] = 1
		x = []
		for i in a:
			if i not in d:
				continue
			x.append(i)
		if x == []:
			return n + m
		s = [x[0]]
		for i in range(1, len(x)):
			if x[i] > s[-1]:
				s.append(x[i])
			else:
				z = bisect.bisect_left(s, x[i])
				s[z] = x[i]
		return n + m - 2 * len(s)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, M) = map(int, input().split())
		A = list(map(int, input().split()))
		B = list(map(int, input().split()))
		ob = Solution()
		print(ob.minInsAndDel(A, B, N, M))


import bisect

class Solution:

	def LISLength(self, v):
		if len(v) == 0:
			return 0
		tail = [0 for i in range(len(v) + 1)]
		length = 1
		tail[0] = v[0]
		for i in range(1, len(v)):
			if v[i] > tail[length - 1]:
				tail[length] = v[i]
				length += 1
			else:
				tail[bisect.bisect_left(tail, v[i], 0, length - 1)] = v[i]
		return length

	def minInsAndDel(self, A, B, N, M):
		mp = dict()
		for i in range(M):
			mp[B[i]] = i
		res = []
		for i in range(N):
			if A[i] in mp:
				res.append(mp[A[i]])
		ans = N - self.LISLength(res) + (M - self.LISLength(res))
		return ans
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(N, M) = map(int, input().split())
		A = list(map(int, input().split()))
		B = list(map(int, input().split()))
		ob = Solution()
		print(ob.minInsAndDel(A, B, N, M))


from bisect import *

class Solution:

	def minInsAndDel(self, A, B, N, M):
		b = set(B)
		lis = []
		for e in filter(lambda x: x in b, A):
			if not lis or e > lis[-1]:
				lis.append(e)
			elif e <= lis[0]:
				lis[0] = e
			else:
				lis[bisect_left(lis, e)] = e
		return N + M - 2 * len(lis)


from collections import defaultdict

def bs(a, x):
	l = 0
	r = len(a) - 1
	ans = float('inf')
	while l <= r:
		mid = (l + r) // 2
		if a[mid] >= x:
			ans = mid
			r = mid - 1
		else:
			l = mid + 1
	return ans

def inc(a):
	n = len(a)
	if n == 0:
		return 0
	s = []
	s.append(a[0])
	for i in range(n):
		place = bs(s, a[i])
		if place == float('inf'):
			s.append(a[i])
		else:
			s[place] = a[i]
	return len(s)

class Solution:

	def minInsAndDel(self, A, B, N, M):
		present = defaultdict(int)
		for x in B:
			present[x] = 1
		a = []
		for x in A:
			if present[x]:
				a.append(x)
		common = inc(a)
		ans = N - common
		ans += M - common
		return ans


class Solution:

	def minInsAndDel(self, A, B, N, M):
		b_set = set()
		for b in B:
			b_set.add(b)
		a_updated = []
		steps = 0
		for i in range(N):
			if A[i] in b_set:
				a_updated.append(A[i])
			else:
				steps += 1
		lis_size = self.LIS(a_updated)
		return steps + (len(a_updated) - lis_size) + (M - lis_size)

	def LIS(self, nums):

		def binarySearch(sub, val):
			(lo, hi) = (0, len(sub) - 1)
			while lo <= hi:
				mid = lo + (hi - lo) // 2
				if sub[mid] < val:
					lo = mid + 1
				elif val < sub[mid]:
					hi = mid - 1
				else:
					return mid
			return lo
		sub = []
		for val in nums:
			pos = binarySearch(sub, val)
			if pos == len(sub):
				sub.append(val)
			else:
				sub[pos] = val
		return len(sub)


from bisect import bisect, bisect_left
from collections import Counter

class Solution:

	def minInsAndDel(self, a, b, n, m):
		ans = []
		c = Counter(b)
		for i in range(n):
			if c[a[i]] == 0:
				continue
			if len(ans) == 0:
				ans = [a[i]]
				continue
			if ans[-1] < a[i]:
				ans.append(a[i])
			else:
				k = bisect_left(ans, a[i])
				ans[k] = a[i]
		return n + m - 2 * len(ans)


class Solution:

	def minInsAndDel(self, arr, brr, n, m):

		def lis(arr, n):
			if n == 0:
				return 0
			t = [arr[0]]

			def ind(t, val, n):
				i = 0
				j = n - 1
				while i <= j:
					m = (i + j) // 2
					if t[m] == val:
						return m
					elif t[m] < val:
						i = m + 1
					else:
						j = m - 1
				return i
			c = 1
			for i in range(1, n):
				if arr[i] > t[-1]:
					t.append(arr[i])
					c += 1
				else:
					te = ind(t, arr[i], c)
					t[te] = arr[i]
			return c
		d = [-1 for i in range(10 ** 5 + 1)]
		for i in range(m):
			d[brr[i]] = i
		t = []
		c = 0
		for val in arr:
			if d[val] != -1:
				t.append(d[val])
				c += 1
		return n + m - 2 * lis(t, c)


import bisect

class Solution:

	def minInsAndDel(self, A, B, N, M):
		newA = []
		setB = set(B)
		for i in A:
			if i in setB:
				newA.append(i)
		removed = len(A) - len(newA)
		lis = []
		for i in newA:
			x = bisect.bisect_left(lis, i)
			if x == len(lis):
				lis.append(i)
			else:
				lis[x] = i
		removed += len(newA) - len(lis)
		inserted = len(B) - len(lis)
		return removed + inserted


class Solution:

	def minInsAndDel(self, A, B, N, M):
		c = []
		s = set(B)
		for i in range(len(A)):
			if A[i] in s:
				c.append(A[i])
		nums = c
		if len(c) == 0:
			return M + N
		a = []
		a.append(nums[0])
		for i in range(1, len(nums)):
			if nums[i] > a[-1]:
				a.append(nums[i])
			else:
				low = 0
				high = len(a) - 1
				while low <= high:
					mid = (low + high) // 2
					if a[mid] < nums[i]:
						low = mid + 1
					else:
						high = mid - 1
				a[low] = nums[i]
		return len(A) + len(B) - 2 * len(a)


class Solution:

	def lcs(self, nums):

		def binary(temp, l, r, target):
			while r >= l:
				mid = (l + r) // 2
				if temp[mid] == target:
					return mid
				elif temp[mid] > target:
					r = mid - 1
				else:
					l = mid + 1
			return l
		temp = [nums[0]]
		for i in range(1, len(nums)):
			if nums[i] > temp[-1]:
				temp.append(nums[i])
			else:
				indx = binary(temp, 0, len(temp) - 1, nums[i])
				temp[indx] = nums[i]
		return len(temp)

	def minInsAndDel(self, a, b, N, M):
		res = {}
		for i in range(M):
			res[b[i]] = i
		ans = []
		count = 0
		for j in range(N):
			if a[j] in res:
				ans.append(a[j])
			else:
				count += 1
		if len(ans) == 0:
			return count + M
		indx = self.lcs(ans)
		return count + (len(ans) - indx) + (M - indx)


import bisect

class Solution:

	def minInsAndDel(self, A, B, N, M):
		l = []
		for i in range(len(A)):
			z = bisect.bisect_left(B, A[i])
			if z < len(B) and B[z] == A[i]:
				l.append(A[i])
		res = []
		if l:
			res.append(l[0])
		for i in range(1, len(l)):
			if res[-1] < l[i]:
				res.append(l[i])
			else:
				x = bisect.bisect_left(res, l[i])
				res[x] = l[i]
		return abs(N + M - 2 * len(res))


class Solution:

	def minInsAndDel(self, A, B, N, M):
		t = []
		B = set(B)
		for a in A:
			if a in B:
				if len(t) == 0 or t[-1] < a:
					t.append(a)
				else:
					i = self.binary_search(t, a, 0, len(t) - 1)
					t[i + 1] = a
		return N + M - 2 * len(t)

	def binary_search(self, t, a, l, h):
		if l > h:
			return h
		mid = (l + h) // 2
		if t[mid] < a:
			return self.binary_search(t, a, mid + 1, h)
		else:
			return self.binary_search(t, a, l, mid - 1)


from bisect import bisect_left

class Solution:

	def minInsAndDelNaive(self, A, B, N, M):
		prev_ops = [0] * (M + 1)
		for i in range(1, M + 1):
			prev_ops[i] = i
		for i in range(N):
			curr_ops = [0] * (M + 1)
			curr_ops[0] = i + 1
			index = self.search(A[i], B, M)
			if index == -1:
				left_val = M + 1
			else:
				left_val = index + 1
			for j in range(1, left_val):
				curr_ops[j] = prev_ops[j] + 1
			if index != -1:
				curr_ops[index + 1] = prev_ops[index]
			for j in range(left_val + 1, M + 1):
				curr_ops[j] = min(curr_ops[j - 1] + 1, prev_ops[j] + 1)
			prev_ops = curr_ops
		return prev_ops[M]

	def search(self, val, arr, N):
		l = 0
		r = N - 1
		while l <= r:
			mid = l + (r - l) // 2
			if arr[mid] == val:
				return mid
			elif val < arr[mid]:
				r = mid - 1
			else:
				l = mid + 1
		return -1

	def minInsAndDel(self, A, B, N, M):
		len_arr = [-1] * M
		curr_len = 0
		for i in range(N):
			index = bisect_left(B, A[i])
			if index == M or B[index] != A[i]:
				continue
			if curr_len == 0:
				len_arr[curr_len] = index
				curr_len += 1
				continue
			elif len_arr[curr_len - 1] < index:
				len_arr[curr_len] = index
				curr_len += 1
			else:
				ceil_len = bisect_left(len_arr, index, 0, curr_len)
				len_arr[ceil_len] = index
		return N + M - 2 * curr_len

	def binary_index_search(self, len_arr, start, end, arr, val):
		l = start
		r = end - 1
		ans = end
		while l <= r:
			mid = l + (r - l) // 2
			if arr[len_arr[mid]] >= val:
				ans = mid
				r = mid - 1
			else:
				l = mid + 1
		return ans


class Solution:

	def minInsAndDel(self, A, B, N, M):
		chk = set(B)
		lst = []
		ans = 0
		for i in A:
			if i in chk:
				lst.append(i)
			else:
				ans += 1
		lis = [0] * len(lst)
		size = 0
		for x in lst:
			(i, j) = (0, size)
			while i < j:
				mid = (i + j) // 2
				if lis[mid] < x:
					i = mid + 1
				else:
					j = mid
			lis[i] = x
			size = max(size, i + 1)
		ans += len(lst) - size + len(B) - size
		return ans


class Solution:

	def minInsAndDel(self, A, B, N, M):
		B = set(B)
		a = []
		steps = 0
		for n in A:
			if n not in B:
				steps += 1
			else:
				a.append(n)
		seq = []
		for n in a:
			if not seq or seq[-1] < n:
				seq.append(n)
			else:
				idx = self.binary_search(seq, n)
				seq[idx] = n
		return steps + len(a) - len(seq) + len(B) - len(seq)

	def binary_search(self, seq, n):
		lo = 0
		hi = len(seq) - 1
		while lo <= hi:
			mid = lo + (hi - lo) // 2
			if seq[mid] < n:
				lo = mid + 1
			elif seq[mid] > n:
				hi = mid - 1
			else:
				return mid
		return lo


from bisect import bisect_left as bl

class Solution:

	def findLIS2(self, a):
		tailTable = [a[0]]
		for i in range(1, len(a)):
			if a[i] < tailTable[0]:
				tailTable[0] = a[i]
			elif a[i] > tailTable[-1]:
				tailTable.append(a[i])
			else:
				tailTable[bl(tailTable, a[i])] = a[i]
		return tailTable

	def findLIS(self, a):
		l = [[a[0]]]
		tailTable = [a[0]]
		for i in range(len(a)):
			smallest = bl(tailTable, a[i])
			if smallest == 0:
				l[0] = [a[i]]
				tailTable[0] = a[i]
			elif smallest == len(l):
				l.append(l[-1] + [a[i]])
				tailTable.append(a[i])
			else:
				l[smallest] = l[smallest - 1] + [a[i]]
				tailTable[smallest] = a[i]
		return l[-1] if l else []

	def minInsAndDel(self, A, B, N, M):
		if A == B:
			return 0
		count = set()
		for el in B:
			count.add(el)
		new_A = []
		for (i, el) in enumerate(A):
			if el in count:
				new_A.append(el)
		if new_A:
			LIS = self.findLIS2(new_A)
			return N + M - 2 * len(LIS)
		else:
			return N + M


from bisect import bisect_left

class Solution:

	def minInsAndDel(self, a, b, n, m):
		c = [x for x in a if self.in_sorted_array(b, x)]
		length = self.lis_length(c)
		deletions = n - length
		insertions = m - length
		return deletions + insertions

	def in_sorted_array(self, b, x):
		i = bisect_left(b, x)
		return i < len(b) and b[i] == x

	def lis_length(self, a):
		s = []
		for x in a:
			if len(s) == 0 or x > s[-1]:
				s.append(x)
			else:
				i = bisect_left(s, x)
				s[i] = x
		return len(s)


from bisect import bisect_left

class Solution:

	def minInsAndDel(self, a, b, n, m):
		ab = self.a_in_b(a, b)
		length = self.lis_length(ab)
		return n - length + m - length

	def a_in_b(self, a, b):
		ab = []
		for x in a:
			i = bisect_left(b, x)
			if i < len(b) and b[i] == x:
				ab.append(x)
		return ab

	def lis_length(self, a):
		s = []
		for x in a:
			if len(s) == 0 or x > s[-1]:
				s.append(x)
			else:
				i = bisect_left(s, x)
				s[i] = x
		return len(s)


from collections import Counter
from functools import lru_cache
from bisect import bisect, bisect_left

class Solution:

	def minInsAndDel(self, A1, B, N, M):
		dc = Counter(B)
		ans = 0
		A = []
		for nm in A1:
			if dc[nm] > 0:
				A.append(nm)
				ans = 1
		n = len(A)
		dp = [1] * n
		final = []
		for i in range(n):
			pos = bisect_left(final, A[i])
			if pos == len(final):
				final.append(A[i])
			else:
				final[pos] = A[i]
		if len(final):
			ans = len(final)
		return len(A1) + len(B) - 2 * ans


class Solution:

	def minInsAndDel(self, nums, nums2, M, N):
		dp = [-1] * M
		dp[-1] = 1

		def LIS(nums):
			tails = [0] * len(nums)
			size = 0
			for x in nums:
				(i, j) = (0, size)
				while i != j:
					m = (i + j) // 2
					if tails[m] < x:
						i = m + 1
					else:
						j = m
				tails[i] = x
				size = max(i + 1, size)
			return size
		s = []
		temp = set(nums2)
		for i in nums:
			if i in temp:
				s.append(i)
		res = LIS(s)
		return M + N - 2 * res


class Solution:

	def minInsAndDel(self, A, B, N, M):
		a = []
		b = set(B)
		steps = 0
		for x in A:
			if x in b:
				a.append(x)
			else:
				steps += 1
		lis = []
		for x in a:
			if not lis or lis[-1] < x:
				lis.append(x)
			else:
				idx = self.binary_search(lis, x)
				lis[idx] = x
		return steps + len(a) - len(lis) + M - len(lis)

	def binary_search(self, arr, x):
		lo = 0
		hi = len(arr) - 1
		while lo <= hi:
			mid = lo + (hi - lo) // 2
			if arr[mid] == x:
				return mid
			elif arr[mid] > x:
				hi = mid - 1
			else:
				lo = mid + 1
		return lo


from bisect import bisect_left

class Solution:

	def minInsAndDel(self, A, B, N, M):

		def lis(v):
			res = []
			if len(v) > 0:
				res.append(v[0])
			for i in range(len(v)):
				if v[i] > res[-1]:
					res.append(v[i])
				else:
					it = bisect_left(res, v[i])
					res[it] = v[i]
			return len(res)

		def trim(a, b):
			res = []
			for i in range(len(a)):
				it = bisect_left(b, a[i])
				if it < len(b) and b[it] == a[i]:
					res.append(a[i])
			return res
		res = trim(A, B)
		return N + M - 2 * lis(res)


import bisect

class Solution:

	def minInsAndDel(self, A, B, N, M):

		def bisect_left(arr, key):
			l = 0
			r = len(arr) - 1
			while l <= r:
				mid = l + (r - l) // 2
				if arr[mid] == key:
					return mid
				if key < arr[mid]:
					r = mid - 1
				else:
					l = mid + 1
			return l

		def LIS(arr):
			n = len(arr)
			stack = []
			if n:
				stack.append(arr[0])
			for i in range(1, n):
				el = arr[i]
				if el > stack[-1]:
					stack.append(el)
				else:
					ind = bisect_left(stack, el)
					stack[ind] = el
			return len(stack)
		A_now = []
		set_B = set(B)
		for el in A:
			if el in set_B:
				A_now.append(el)
		lis = LIS(A_now)
		op = N + M - 2 * lis
		return op


import bisect

class Solution:

	def minInsAndDel(self, A, B, N, M):

		def bisect_left(arr, key):
			l = 0
			r = len(arr) - 1
			while l <= r:
				mid = l + (r - l) // 2
				if arr[mid] == key:
					return mid
				if key < arr[mid]:
					r = mid - 1
				else:
					l = mid + 1
			return r

		def LIS(arr):
			stack = []
			for el in arr:
				if stack and stack[-1] > el:
					ind = bisect_left(stack, el)
					stack[ind] = el
				else:
					stack.append(el)
			return len(stack)

		def lis(a):
			list = []
			if len(a) > 0:
				list.append(a[0])
			for i in range(1, len(a)):
				if a[i] > list[-1]:
					list.append(a[i])
				else:
					x = bisect.bisect_left(list, a[i])
					list[x] = a[i]
			return len(list)
		dict = {}
		for i in B:
			dict[i] = 1
		list = []
		for i in A:
			if dict.get(i) != None:
				list.append(i)
		a = lis(list)
		return N + M - 2 * a


from bisect import bisect_left

def LISL(v):
	if len(v) == 0:
		return 0
	tail = [0 for i in range(len(v) + 1)]
	length = 1
	tail[0] = v[0]
	for i in range(1, len(v)):
		if v[i] > tail[length - 1]:
			tail[length] = v[i]
			length += 1
		else:
			tail[bisect_left(tail, v[i], 0, length - 1)] = v[i]
	return length

class Solution:

	def minInsAndDel(self, A, B, N, M):
		vec = []
		s = set(B)
		for i in A:
			if i in s:
				vec.append(i)
		res = LISL(vec)
		return abs(N - res) + abs(M - res)


import bisect

def lis(a):
	list = []
	if len(a) > 0:
		list.append(a[0])
	for i in range(1, len(a)):
		if a[i] > list[-1]:
			list.append(a[i])
		else:
			x = bisect.bisect_left(list, a[i])
			list[x] = a[i]
	return len(list)

class Solution:

	def minInsAndDel(self, A, B, N, M):
		dict = {}
		for i in B:
			dict[i] = 1
		list = []
		for i in A:
			if dict.get(i) != None:
				list.append(i)
		a = lis(list)
		return N + M - 2 * a


from bisect import bisect_left

def LongestIncreasingSubsequenceLength(nums):
	sub = []
	for x in nums:
		if len(sub) == 0 or sub[-1] < x:
			sub.append(x)
		else:
			idx = bisect_left(sub, x)
			sub[idx] = x
	return len(sub)

class Solution:

	def minInsAndDel(self, arr, brr, N, M):
		vec = []
		s = set(brr)
		for i in arr:
			if i in s:
				vec.append(i)
		res = LongestIncreasingSubsequenceLength(vec)
		return abs(N - res) + abs(M - res)


from bisect import bisect_left as bl

class Solution:

	def minInsAndDel(self, a, b, n, m):
		vis = set()
		for num in b:
			vis.add(num)
		lis = []
		for num in a:
			if num in vis:
				idx = bl(lis, num)
				if idx == len(lis):
					lis.append(num)
				else:
					lis[idx] = num
		return n + m - 2 * len(lis)


from bisect import bisect_left

def lis(B):
	if len(B) == 0:
		return 0
	temp = [B[0]]
	for i in B:
		if i > temp[-1]:
			temp.append(i)
		else:
			ind = bisect_left(temp, i, 0, len(temp))
			temp[ind] = i
	return len(temp)

class Solution:

	def minInsAndDel(self, A, B, N, M):
		temp = []
		set_B = set(B)
		for i in A:
			if i in set_B:
				temp.append(i)
		l = lis(temp)
		return N + M - 2 * l


from bisect import bisect_left

class Solution:

	def minInsAndDel(self, A, B, N, M):
		s = set(B)
		a = [x for x in A if x in s]
		(p, r) = ([0] * len(a), [])
		for (i, x) in enumerate(a):
			j = bisect_left(r, (x, 0))
			if j == len(r):
				r.append((x, i))
				j = len(r) - 1
			(r[j], p[i]) = ((x, i), r[j - 1][1] if j > 0 else 0)
		(ans, c) = ([0] * len(r), r[-1][1] if r else 0)
		for i in range(len(r) - 1, -1, -1):
			(ans[i], c) = (c, p[c])
		return N + M - 2 * len(ans)


from bisect import bisect_left

class Solution:

	def minInsAndDel(self, A, B, N, M):
		s = set(B)
		x = []
		y = 0
		for i in range(N):
			if A[i] in s:
				a = bisect_left(x, A[i])
				if a == y:
					x.append(A[i])
					y += 1
				else:
					x[a] = A[i]
		z = 2 * len(x)
		return N + M - z


from bisect import bisect_left

class Solution:

	def minInsAndDel(self, A, B, N, M):
		lis = []
		c = 0
		s = set(B)
		for i in range(N):
			if A[i] in s:
				it = bisect_left(lis, A[i])
				if it == c:
					lis.append(A[i])
					c += 1
				else:
					lis[it] = A[i]
		return N + M - 2 * len(lis)