#include <iostream>
#include <algorithm>
#include <utility>
using namespace std;
void print(int a[], int n)
{
for (int i = 0; i < n; i++)
{
cout << a[i] << " ";
}
cout << endl;
}
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l)
{
int mid = l + (r - l) / 2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
return binarySearch(arr, mid + 1, r, x);
}
return l;
}
int main()
{
int r = 0;
int n, m;
cin >> n >> m;
int *a = new int[n + m];
int *k = new int[m];
int p = 0;
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
for (int i = 0; i < m; i++)
{
cin >> k[i];
}
int index;
while (p < m)
{
if (k[p] >= a[n + p - 1])
{
a[n + p] = k[p];
p++;
}
else
{
index = binarySearch(a, 0, n + m, k[p]);
while (a[index] <= k[p])
{
index++;
}
r++;
swap(k[p], a[index]);
}
}
cout << r << endl;
return 0;
}
Copy