Swaps solution codeforces
You are given two arrays odd integer from to in an arbitrary order, and array contains each even integer from to in an arbitrary order.and of length . Array contains each
You can perform the following operation on those arrays:
- choose one of the two arrays
- pick an index from to
- swap the -th and the -th elements of the chosen array
Compute the minimum number of operations needed to make arraylexicographically smaller than array .For two different arrays and of the same length , we say that is lexicographically smaller than if in the first position where and differ, the array has a smaller element than the corresponding element in .
Each test contains multiple test cases. The first line contains the number of test cases( ).
The first line of each test case contains a single integer( ) — the length of the arrays.
The second line of each test case contains odd and pairwise distinct) — array .integers ( , all are
The third line of each test case contains even and pairwise distinct) — array .integers ( , all are
It is guaranteed that the sum ofover all test cases does not exceed .
For each test case, print one integer: the minimum number of operations needed to make arraylexicographically smaller than array .
We can show that an answer always exists.
Example Swaps solution codeforces
input Swaps solution codeforces
3 2 3 1 4 2 3 5 3 1 2 4 6 5 7 5 9 1 3 2 4 6 10 8
In the first example, the arrayis already lexicographically smaller than array , so no operations are required.
In the second example, we can swapand and then swap and , which results in and . Another correct way is to swap and and then swap and , which results in and . Yet another correct way is to swap and and then swap and , which results in and .