Swaps
Contest: Codeforces Round 743 (Div. 2)
Difficulty rating: 1400
Tags: greedy, math, sortings

You are given two arrays $$$a$$$ and $$$b$$$ of length $$$n$$$. Array $$$a$$$ contains each odd integer from $$$1$$$ to $$$2n$$$ in an arbitrary order, and array $$$b$$$ contains each even integer from $$$1$$$ to $$$2n$$$ in an arbitrary order.

You can perform the following operation on those arrays:

- choose one of the two arrays
- pick an index $$$i$$$ from $$$1$$$ to $$$n-1$$$
- swap the $$$i$$$-th and the $$$(i+1)$$$-th elements of the chosen array

For two different arrays $$$x$$$ and $$$y$$$ of the same length $$$n$$$, we say that $$$x$$$ is lexicographically smaller than $$$y$$$ if in the first position where $$$x$$$ and $$$y$$$ differ, the array $$$x$$$ has a smaller element than the corresponding element in $$$y$$$.

Input format:
Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$).

The first line of each test case contains a single integer $$$n$$$ ($$$1 \le n \le 10^5$$$) — the length of the arrays.

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 2n$$$, all $$$a_i$$$ are odd and pairwise distinct) — array $$$a$$$.

The third line of each test case contains $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le 2n$$$, all $$$b_i$$$ are even and pairwise distinct) — array $$$b$$$.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^5$$$.

Output format:
For each test case, print one integer: the minimum number of operations needed to make array $$$a$$$ lexicographically smaller than array $$$b$$$.

We can show that an answer always exists.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first example, the array $$$a$$$ is already lexicographically smaller than array $$$b$$$, so no operations are required.

In the second example, we can swap $$$5$$$ and $$$3$$$ and then swap $$$2$$$ and $$$4$$$, which results in $$$[3, 5, 1]$$$ and $$$[4, 2, 6]$$$. Another correct way is to swap $$$3$$$ and $$$1$$$ and then swap $$$5$$$ and $$$1$$$, which results in $$$[1, 5, 3]$$$ and $$$[2, 4, 6]$$$. Yet another correct way is to swap $$$4$$$ and $$$6$$$ and then swap $$$2$$$ and $$$6$$$, which results in $$$[5, 3, 1]$$$ and $$$[6, 2, 4]$$$.

Example input:
3
2
3 1
4 2
3
5 3 1
2 4 6
5
7 5 9 1 3
2 4 6 10 8

Example output:
0
2
3

Editorial:
Since the array $$$a$$$ has odd numbers and array $$$b$$$ has even numbers, then they will differ at the first position no matter how we perform the operations. It follows that in order to make the first array lexicographically smaller than the second one we need to make the first element of $$$a$$$ smaller than the first element of $$$b$$$. To move the $$$i$$$-th element of an array to the first position we can perform the operation on elements $$$i - 1$$$, $$$i - 2$$$, ..., $$$2$$$, $$$1$$$, which is optimal. The answer is then the minimum of $$$i + j - 2$$$ over all $$$a_i$$$, $$$b_j$$$ such that $$$a_i < b_j$$$.
Now we will think how to calculate this effectively. Let $$$p_i$$$ be the position of number $$$i$$$ in its respective sequence ($$$a$$$ for odd and $$$b$$$ for even). We will go through the numbers from biggest to smallest. Let $$$l$$$ be the position of the leftmost number in sequence $$$b$$$ that was already considered. If $$$i$$$ is even we will set $$$l$$$ to $$$min(l, p_i)$$$. If $$$i$$$ is odd we will set $$$answer$$$ to $$$min(answer, p_i + l)$$$.
Our total time complexity is then $$$O(n)$$$.