Codeforces Round 751 (Div. 1) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

data structures

divide and conquer

dp

greedy

sortings

*2300

No tag edit access

The problem statement has recently been changed. View the changes.

×
C. Optimal Insertion

time limit per test

3 secondsmemory limit per test

512 megabytesinput

standard inputoutput

standard outputYou 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

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.

Output

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

Example

Input

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

Output

0 4 6

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 = [\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]$$$.

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/13/2024 10:27:17 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|