У вас есть два массива $$$a_1, a_2, \ldots, a_n$$$ и $$$b_1, b_2, \ldots, b_m$$$, состоящие из целых чисел.
Вы должны вставить все элементы массива $$$b$$$ в массив $$$a$$$ в произвольные места. В результате получится массив $$$c_1, c_2, \ldots, c_{n+m}$$$ размера $$$n + m$$$.
Обратите внимание, что элементы массива $$$a$$$ переставлять нельзя, а элементы массива $$$b$$$ можно вставлять куда угодно (в начало, между двумя соседними элементами массива $$$a$$$, в конец) и между собой они могут быть расположены в произвольном порядке.
Какое минимальное количество инверсий в массиве $$$c$$$ может быть? Напомним, что инверсией называется пара индексов $$$(i, j)$$$, такая что $$$i \lt j$$$ и $$$c_i \gt c_j$$$.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следуют описания наборов входных данных.
В первой строке описания каждого набора входных данных находятся два целых числа $$$n$$$, $$$m$$$ ($$$1 \leq n, m \leq 10^6$$$).
Во второй строке описания каждого набора входных данных находятся $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$).
Во третьей строке описания каждого набора входных данных находятся $$$m$$$ целых чисел $$$b_1, b_2, \ldots, b_m$$$ ($$$1 \leq b_i \leq 10^9$$$).
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^6$$$ и сумма $$$m$$$ по всем наборам входных данных не превосходит $$$10^6$$$.
Для каждого набора входных данных выведите одно целое число — минимальное количество инверсий, которое может получиться в массиве $$$c$$$ при вставке.
3 3 4 1 2 3 4 3 2 1 3 3 3 2 1 1 2 3 5 4 1 3 5 3 1 4 3 6 1
0 4 6
Варианты оптимальных вставок для всех наборов входных данных (жирным выделены элементы массива $$$a$$$):
