CF1601C 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 $ .

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 = [\underline{1}, 1, \underline{2}, 2, \underline{3}, 3, 4] $ . - In the second test case, $ c = [1, 2, \underline{3}, \underline{2}, \underline{1}, 3] $ . - In the third test case, $ c = [\underline{1}, 1, 3, \underline{3}, \underline{5}, \underline{3}, \underline{1}, 4, 6] $ .