B. Swaps＜743,div2＞

B. Swaps

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given two arrays aa and bb of length nn. Array aa contains each odd integer from 11 to 2n2n in an arbitrary order, and array bb contains each even integer from 11 to 2n2n in an arbitrary order.

You can perform the following operation on those arrays:

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

Compute the minimum number of operations needed to make array aa lexicographically smaller than array bb.

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

Input

Each test contains multiple test cases. The first line contains the number of test cases tt (1≤t≤1041≤t≤104).

The first line of each test case contains a single integer nn (1≤n≤1051≤n≤105) — the length of the arrays.

The second line of each test case contains nn integers a1,a2,…,ana1,a2,…,an (1≤ai≤2n1≤ai≤2n, all aiai are odd and pairwise distinct) — array aa.

The third line of each test case contains nn integers b1,b2,…,bnb1,b2,…,bn (1≤bi≤2n1≤bi≤2n, all bibi are even and pairwise distinct) — array bb.

It is guaranteed that the sum of nn over all test cases does not exceed 105105.

Output

For each test case, print one integer: the minimum number of operations needed to make array aa lexicographically smaller than array bb.

We can show that an answer always exists.

Example

input

Copy

3

2

3 1

4 2

3

5 3 1

2 4 6

5

7 5 9 1 3

2 4 6 10 8

output

Copy

0

2

3

Note

In the first example, the array aa is already lexicographically smaller than array bb, so no operations are required.

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

#include <bits/stdc++.h>
using namespace std;
int a[1000005], b[1000005];
int main() {
  int t;
  cin >> t;
  while (t--) {
    map<int, int>mp;
    int mixn = 0, minxx = 100000007, minxf = 100000007;
    int n;
    cin >> n;
    for (int i = 0; i < n; i++) {
      cin >> a[i];
      mp[a[i]] = i;
    }
    sort(a, a + n);
    for (int i = 0; i < n; i++) {
      cin >> b[i];
      mp[b[i]] = i;
    }
    sort(b, b + n);
    for (int i = 0; i < n; i++) {
      if (mp[a[i]] < minxx) {
        minxx = mp[a[i]];
      }
      mixn = mp[b[i]] + minxx;
      if (mixn < minxf) {
        minxf = mixn;
      }
    }
    cout << minxf << endl;
  }
}