A14581 | Optimal Insertion

You are given two arrays of integers $a_1, a_2, \ldots, a_n$ and $b_1, b_2, \ldots, b_m$ .

You need to insert all elements of $b$ into $a$ in an arbitrary way. As a result you will get an array $c_1, c_2, \ldots, c_{n+m}$ of size $n + m$ .

Note that you are not allowed to change the order of elements in $a$ , while you can insert elements of $b$ at arbitrary positions. They can be inserted at the beginning, between any elements of $a$ , or at the end. Moreover, elements of $b$ can appear in the resulting array in any order.

What is the minimum possible number of inversions in the resulting array $c$ ? Recall that an inversion is a pair of indices $(i, j)$ such that $i < j$ and $c_i > c_j$ .

Each test contains multiple test cases. The first line contains the number of test cases $t$ ( $1 \leq t \leq 10^4$ ). Description of the test cases follows.

The first line of each test case contains two integers $n$ and $m$ ( $1 \leq n, m \leq 10^6$ ).

The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $1 \leq a_i \leq 10^9$ ).

The third line of each test case contains $m$ integers $b_1, b_2, \ldots, b_m$ ( $1 \leq b_i \leq 10^9$ ).

It is guaranteed that the sum of $n$ for all tests cases in one input doesn't exceed $10^6$ . The sum of $m$ for all tests cases doesn't exceed $10^6$ as well.

For each test case, print one integer — the minimum possible number of inversions in the resulting array $c$ .