Salmon received an array $A$ of size $N$ and an array $B$ of size $M$ for Christmas. He would like to move all the elements in $B$ to $A$ using a special method described below.

While $B$ is not empty, Salmon does the following operations in order:

* Remove and store the leftmost element off of B (let's call this element $X$).
* Place $X$ at the start of $A$.
* Keep swapping $X$ and the element to the right of it repeatedly until $X$ is at the rightmost position of $A$ or $X$ is greater or equal to the element to the right of it.

Before performing the operations, Salmon can rearrange both A and B in any order once. He would like to do as little work as possible -- determine the minimum possible amount of swaps.

------ Input: ------
The first line of input will consist of a two space-separated integers, $N$ and $M$ ($1 ≤ N, M ≤ 2*10^{5}$).

The next line will consist of $N$ space-separated integers, with the $i$-th input representing $A[i]$ ($-10^{9} ≤ A[i] ≤ 10^{9}$).

The next line will consist of $M$ space-separated integers, with the $i$-th input representing $B[i]$ ($-10^{9} ≤ B[i] ≤ 10^{9}$).

------ Output: ------
Output a single integer, the minimum number of swaps required.

------ Subtasks: ------
* Subtask 1 [15 points]: $A[i] = 1, B[i] = 1$ for all $i$.
* Subtask 2 [30 points]: $N, M ≤ 10^{3}$.
* Subtask 3 [55 points]: No additional constraints.

------ Note: ------
The answer may be greater than the limit for a 32-bit integer. Use long long instead of int for C++ and long for Java. Please check your language documentation for other languages on how to use 64-bit integers. Note that Python solutions won't encounter a problem as it uses BigIntegers by default.

----- Sample Input 1 ------ 
5 3
10 5 2 5 4
3 1 2
----- Sample Output 1 ------ 
5
----- explanation 1 ------ 
Salmon can reorder $A$ to be $[2, 10, 5, 4, 5]$ and $B$ to be $[1, 2, 3]$.

Difficulty: MEDIUM_HARD
Tags: Constructive algorithms

Ad-hoc

Starter code:

Solutions:
(na, nb) = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
b = list(map(int, input().split(' ')))
res = 0
comp = min(a)
for value in b:
	if value < comp:
		res += na
print(res)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
m = min(a)
c = sum((1 for x in b if x < m))
print(c * len(a))


(N, M) = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))
ma = min(A)
x = 0
for i in B:
	if i < ma:
		x += N
print(x)


def soln(n, m, a, b):
	b.sort()
	a_min = min(a)
	res = i = 0
	while i < m and b[i] < a_min:
		res += n
		i += 1
	return res
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
print(soln(n, m, a, b))


(ms, mn) = map(int, input().split())
lm = list(map(int, input().split()))
ln = list(map(int, input().split()))
n = min(lm)
ln.sort()
c = 0
for i in ln:
	if i >= n:
		break
	c += ms
print(c)


(msn, msm) = map(int, input().split())
n = list(map(int, input().split()))
m = list(map(int, input().split()))
n_min = min(n)
m.sort()
c = 0
for i in m:
	if i >= n_min:
		break
	c += msn
print(c)


(N, M) = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
temp = min(A)
count = 0
for i in B:
	if i < temp:
		count += 1
print(count * N)


(n, m) = list(map(int, input().split()))
x = input().split()
y = input().split()
for i in range(len(x)):
	x[i] = int(x[i])
for i in range(len(y)):
	y[i] = int(y[i])
s = x[0]
for i in range(len(x)):
	if s > x[i]:
		s = x[i]
count = 0
for i in range(len(y)):
	if y[i] < s:
		count += 1
print(count * n)


(n, m) = list(map(int, input().split()))
a = input().split()
b = input().split()
for i in range(len(a)):
	a[i] = int(a[i])
for i in range(len(b)):
	b[i] = int(b[i])
smol = a[0]
for i in range(len(a)):
	if smol > a[i]:
		smol = a[i]
cnt = 0
for i in range(len(b)):
	if b[i] < smol:
		cnt += 1
print(cnt * n)


(n, m) = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
min_a = min(a)
c = 0
for e in b:
	if e < min_a:
		c += 1
print(c * n)


from bisect import bisect, bisect_left, bisect_right
(n, m) = map(int, input().split())
nli = list(map(int, input().split()))
mli = list(map(int, input().split()))
nli.sort()
mli.sort()
num = nli[0]
nm = bisect_left(mli, num)
print(n * nm)


def solve(A, B):
	A.sort()
	B.sort(reverse=True)
	ans = 0
	while B:
		x = B.pop()
		if x < A[0]:
			ans += n
	print(ans)
for _ in range(1):
	(n, m) = list(map(int, input().split()))
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	solve(A, B)


from collections import Counter

def solve(A, B):
	A.sort()
	dct_b = Counter(B)
	B = list(dct_b.keys())
	B.sort(reverse=True)
	ans = 0
	while B:
		x = B.pop()
		swaps = 0
		if x < A[0]:
			swaps += n
		ans += swaps * dct_b[x]
	print(ans)
for _ in range(1):
	(n, m) = list(map(int, input().split()))
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	solve(A, B)


(n, m) = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
b = [int(j) for j in input().split()]
mn = a[0]
ans = 0
for i in range(1, n):
	mn = min(mn, a[i])
for j in range(0, m):
	if b[j] < mn:
		ans = ans + 1
print(ans * n)


(n, m) = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
a = min(A)
c = 0
l = len(B)
for i in range(l):
	if B[i] < a:
		c += 1
print(c * n)


from sys import stdin, stdout
import math
from collections import Counter
import functools
import time
import bisect

def tr():
	return range(int(line()))

def sm():
	return map(int, line().split())

def ln():
	return list(sm())

def nl():
	return int(line())

def ssm():
	return map(str, line().split())

def line():
	return stdin.readline().rstrip()

def b(x):
	return bin(x).replace('0b', '')

def o(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + '\n')

def osp(x):
	if type(x) != type(''):
		x = str(x)
	stdout.write(x + ' ')

def ol(x):
	stdout.write(' '.join(map(str, x)))

def wline():
	return stdin.read().split()

def main():
	(n, m) = sm()
	a = ln()
	b = ln()
	min_b = min(a)
	count = 0
	for i in b:
		if i < min_b:
			count += 1
	print(count * n)
main()


def solution(A, B):
	A.sort()
	B.sort()
	ans = 0
	for i in range(0, len(B)):
		if B[i] >= A[0]:
			break
		else:
			ans += len(A)
	return ans
_ = input()
A = list(map(int, input().split()))
B = list(map(int, input().split()))
print(solution(A, B))


try:
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	b.sort()
	index = 0
	for i in range(1, n):
		if a[index] > a[i]:
			index = i
	(a[index], a[0]) = (a[0], a[index])
	ans = 0
	for i in range(m):
		if b[i] < a[0]:
			ans += n
	print(ans)
except Exception:
	pass


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
mn = min(a)
cnt = 0
for i in range(0, m):
	if b[i] < mn:
		cnt += 1
print(cnt * n)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a = min(a)
c = 0
for j in range(len(b)):
	if b[j] < a:
		c += 1
print(c * n)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
k = min(a)
c = 0
for i in b:
	if i < k:
		c += 1
print(c * n)


import os.path
import sys
from math import *
from math import floor, gcd, fabs, factorial, fmod, sqrt, inf, log
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def inp():
	return sys.stdin.readline().strip()
for _ in range(1):
	(n, m) = map(int, inp().split())
	a = list(map(int, inp().split()))
	b = list(map(int, inp().split()))
	a.sort()
	b.sort()
	(ans, i) = [0] * 2
	while i < m and b[i] < a[0]:
		ans += 1
		i += 1
	print(ans * n)


(n, m) = list(map(int, input().split()))
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.sort()
b.sort()
ans = 0
for i in range(m):
	if b[i] < a[0]:
		ans += n
print(ans)


(l, m) = map(int, input().split())
arr = list(map(int, input().split()))
brr = list(map(int, input().split()))
brr = sorted(brr)
count = 0
loose = 0
mini = min(arr)
for i in range(m):
	if brr[i] >= mini:
		break
	count += l
print(count)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.sort()
b.sort()
c = a[0]
d = 0
for i in range(n):
	if b[i] < c:
		d += 1
	else:
		break
print(n * d)


(n, m) = (int(o) for o in input().split())
a = [int(o) for o in input().split()]
b = [int(o) for o in input().split()]
mi = min(a)
b.sort()
ans = 0
for i in b:
	if i < mi:
		ans += n
print(ans)


(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
x = 0
z = min(a)
for i in b:
	if i < z:
		x += n
print(x)


try:
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	a.sort()
	b.sort(reverse=True)
	c = 0
	st = 0
	stt = 0
	if b[0] < a[0]:
		c = c + m * n
	else:
		for j in range(m):
			for i in range(n):
				if b[j] > a[i]:
					st = -1
					break
				if b[j] == a[i]:
					c = n * (m - (j + 1))
					st = 1
					if i == 0 and j == 0:
						c = 0
					break
				if b[j] < a[i]:
					st = 2
					c = n * (m - j)
					break
			if st == 1:
				break
			if st == -1:
				continue
			if st == 2:
				break
	print(c)
except:
	pass


def solve(n, m, a, b):
	mn = min(a)
	c = 0
	for i in range(m):
		if b[i] < mn:
			c += 1
	return c * n
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
print(solve(n, m, a, b))


import sys

def get_ints():
	return list(map(int, sys.stdin.readline().strip().split()))
arr = get_ints()
n = arr[0]
m = arr[1]
arra = get_ints()
arrb = get_ints()
arra = sorted(arra)
arrb = sorted(arrb)
mina = min(arra)
ans = 0
for i in arrb:
	if i < mina:
		ans += n
		continue
	for j in arra:
		if i >= j:
			break
		ans += 1
print(ans)


(N, M) = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
A.sort()
B.sort()
x = A[0]
ans = 0
for i in range(len(B)):
	if x > B[i]:
		ans = ans + N
	else:
		break
print(ans)


(n, m) = list(map(int, input().split()))
a = list(map(int, input().split()))
b = sorted(list(map(int, input().split())))
x = min(a)
c = 0
for i in range(m):
	if x > b[i]:
		c = c + n
	else:
		break
print(c)


(N, M) = map(int, input().split())
A = [int(x) for x in input().split()]
B = [int(x) for x in input().split()]
C = min(A)
D = 0
for i in B:
	if i < C:
		D += 1
print(D * N)


(N, M) = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
A.sort()
B.sort()
L = []
flag = 0
for x in B:
	c = 0
	for y in A:
		if x >= A[0]:
			flag = 1
			break
		elif x == A[len(A) - 1]:
			c = len(A) - 1
			break
		elif x < A[len(A) - 1]:
			c = len(A)
			break
		elif x < y:
			c += 1
		else:
			break
	L.append(c)
	if flag == 1:
		break
print(sum(L))


(N, M) = [int(x) for x in input().split()]
A = [int(u) for u in input().split()]
B = [int(u) for u in input().split()]
B.sort()
mina = min(A)
for i in range(len(B)):
	if B[i] >= mina:
		splt_index = i
		break
print(N * splt_index)


(a, b) = map(int, input().split())
arr = list(map(int, input().split()))
brr = list(map(int, input().split()))
m = min(arr)
b = 0
for i in brr:
	if i < m:
		b += a
print(b)


l = input()
m = sorted(list(map(int, input().split())))
n = sorted(list(map(int, input().split())))
a = len(m)
c = 0
for i in range(0, len(n)):
	if n[i] < m[0]:
		c = c + a
	else:
		break
print(c)


from sys import stdin as inp
from sys import stdout as out
(n, m) = list(map(int, inp.readline().split()))
a = list(map(int, inp.readline().split()))
b = list(map(int, inp.readline().split()))
c = 0
m = min(a)
for i in b:
	if i < m:
		c += n
print(c)


(n, m) = map(int, input().split())
l1 = list(map(int, input().split()))
l2 = list(map(int, input().split()))
l1.sort()
l2.sort()
ans = 0
for i in range(m):
	if l2[i] < l1[0]:
		ans += n
	else:
		break
print(ans)


try:
	(n, m) = map(int, input().split())
	a = sorted(list(map(int, input().split())))
	b = sorted(list(map(int, input().split())))
	count = 0
	for i in b:
		if i < a[0]:
			count += n
	print(count)
except:
	pass


(n, m) = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
b = list(map(int, input().split(' ')))
f = min(a)
count = 0
for j in range(m):
	if b[j] < f:
		count += 1
print(count * n)


(n, m) = map(int, input().split())
l = list(map(int, input().split()))
p = list(map(int, input().split()))
l.sort()
p.sort()
x = 0
for i in range(m):
	if p[i] < l[0]:
		x += n
print(x)


def binarySearch(arr, l, r, x):
	mid = 0
	while l <= r:
		mid = l + (r - l) // 2
		if arr[mid] < x:
			l = mid + 1
		else:
			r = mid - 1
	return mid
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
a.sort()
b.sort()
lengthToBeSearched = len(a) - 1
numSwaps = 0
for i in b:
	if i < a[0]:
		numSwaps += len(a)
	else:
		break
print(numSwaps)


try:
	(n, m) = map(int, input().split())
	A = [int(x) for x in input().split()]
	B = [int(x) for x in input().split()]
	B.sort()
	minn = min(A)
	(i, res) = (0, 0)
	while i < m:
		if B[i] < minn:
			res += n
		else:
			break
		i += 1
	print(res)
except EOFError:
	pass


(a, b) = map(int, input().split())
x = list(map(int, input().split()))
y = list(map(int, input().split()))
x.sort()
y.sort()
c = 0
for i in range(len(y)):
	if y[i] < x[0]:
		c += len(x)
print(c)


(N, M) = list(map(int, input().split()))
A = list(map(int, input().split()))
B = list(map(int, input().split()))
a = min(A)
print(N * sum([b < a for b in B]))


(n, m) = map(int, input().split())
a = [int(ele) for ele in input().split()]
b = [int(ele) for ele in input().split()]
c = min(a)
count = 0
for i in b:
	if i < c:
		count += 1
print(count * n)


(n, m) = list(map(int, input().split()))
lst1 = list(map(int, input().split()))
lst2 = list(map(int, input().split()))
v = min(lst1)
s = 0
for i in lst2:
	if i < v:
		s += n
print(s)


(n, m) = map(int, input().split())
arr1 = [int(x) for x in input().split()]
arr2 = [int(x) for x in input().split()]
if sum(arr1) == n and sum(arr2) == m:
	print(0)
else:
	arr1.sort(reverse=True)
	arr2.sort()
	c = 0
	for i in range(0, m):
		if arr2[i] < arr1[n - 1]:
			c = c + 1
	print(c * n)


def arraySwap(n, m, l1, l2):
	l = sorted(l1)
	swap = 0
	s1 = set(l1)
	s2 = set(l2)
	if s1 == 1 and s2 == 1:
		swap = 0
		return swap
	for i in l2:
		X = i
		if X < l[0]:
			swap += n
	return swap
(n, m) = input().split()
l1 = [int(x) for x in input().split()]
l2 = [int(x) for x in input().split()]
print(arraySwap(int(n), int(m), l1, l2))


(n, m) = map(int, input().split())
l = list(map(int, input().split()))
d = list(map(int, input().split()))
x = min(l)
c = 0
for i in range(m):
	if d[i] < x:
		c += 1
print(c * n)


(n, m) = [int(x) for x in input().split()]
arrA = [int(x) for x in input().split()]
arrB = [int(x) for x in input().split()]
a = min(arrA)
C = 0
for i in range(m):
	if arrB[i] < a:
		C += 1
print(C * n)


(n, m) = map(int, input().split())
a = sorted(list(map(int, input().split())))
b = sorted(list(map(int, input().split())))
i = 0
count = 0
for i in range(m):
	if b[i] >= a[0]:
		continue
	else:
		count += n
print(count)


try:
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	b.sort()
	a.sort()
	c = 0
	k = 0
	while k < m:
		if b[k] < a[0]:
			c = c + n
		k = k + 1
	print(c)
except EOFError as e:
	pass


n_m = input().split()
mn = 1000000000.0 + 5
n = int(n_m[0])
m = int(n_m[1])
x = input().split()
y = input().split()
for i in range(n):
	mn = min(mn, int(x[i]))
ops = 0
for i in range(m):
	if int(y[i]) < mn:
		ops += n
print(ops)


(n, m) = map(int, input().split())
l1 = list(map(int, input().split()))
l2 = list(map(int, input().split()))
l1.sort()
l2.sort()
cnt = 0
for i in range(m):
	if l2[i] < l1[0]:
		cnt = cnt + n
print(cnt)


(n, m) = map(int, input().split())
array1 = [int(i) for i in input().split()]
array2 = [int(i) for i in input().split()]
mini = min(array1)
ans = 0
for i in array2:
	if i < mini:
		ans += 1
print(ans * n)


(n, m) = map(int, input().split())
l1 = list(map(int, input().split()))
l2 = list(map(int, input().split()))
a = min(l1)
count = 0
for ele in l2:
	if ele < a:
		count += 1
print(count * n)


(N, M) = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
a = min(A)
c = 0
for i in range(len(B)):
	if B[i] < a:
		c += 1
print(c * N)


try:
	A = []
	B = []
	(N, M) = map(int, input().split())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	A.sort()
	B.sort()
	ans = 0
	for X in B:
		if X >= A[0]:
			break
		ans = ans + N
	print(ans)
except:
	pass


(n, m) = map(int, input().split())
arr = list(map(int, input().split()))
brr = list(map(int, input().split()))
m = min(arr)
c = 0
for x in brr:
	if x < m:
		c += 1
print(c * n)


(n, m) = map(int, input().split())
N = list(map(int, input().split()))
M = list(map(int, input().split()))
N.sort()
M.sort()
Nmin = min(N)
cnt = n
ans = 0
for i in range(m):
	if M[i] < Nmin:
		ans += cnt
print(ans)


(n, m) = list(map(int, input().split()))
n = list(map(int, input().split()))
nm = min(n)
num = list(map(int, input().split()))
count = 0
for i in num:
	if i < nm:
		count += 1
print(count * len(n))


def lower(nums, target):
	start = -1
	low = 0
	high = len(nums) - 1
	while low < high:
		m = low + (high - low) // 2
		if nums[m] >= target:
			start = m
			high -= 1
		else:
			low = m + 1
	return start
(n, m) = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
b.sort()
mn = min(a)
s1 = lower(b, mn)
print(s1 * len(a))