← Home
write a go solution for Description:
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.

Input Format:
Each test contains multiple test cases. The first line contains the number of test cases t (1<=t<=10^4). Description of the test cases follows.

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

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

The third line of each test case contains m integers b_1,b_2,ldots,b_m (1<=b_i<=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.

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

Note:
Below is given the solution to get the optimal answer for each of the example test cases (elements of a are underscored).

- In the first test case, c=[underline1,1,underline2,2,underline3,3,4].
- In the second test case, c=[1,2,underline3,underline2,underline1,3].
- In the third test case, c=[underline1,1,3,underline3,underline5,underline3,underline1,4,6].. Output only the code with no comments, explanation, or additional text.