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

Compute the minimum number of operations needed to make array $a$ lexicographically smaller than array $b$.

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

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

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.


-----Examples-----

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
Output
0
2
3


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

Difficulty: MEDIUM
Tags: Sorting

Mathematics

Greedy algorithms
Skill types: Sorting

Greedy algorithms

Starter code:

Solutions:
def get_input():
	al = []
	for c in range(int(input())):
		input()
		a = [int(i) for i in input().split(' ')]
		b = [int(i) for i in input().split(' ')]
		al.append([a, b])
	return al

def solve(a, b):
	j = 1
	di = {}
	for i in range(len(a)):
		while j < b[i]:
			di[j] = i
			j += 2
	ans = 2 * len(a) + 1
	for i in range(len(a)):
		ans = min(ans, i + di[a[i]])
	return ans

def main():
	arr_list = get_input()
	for (a, b) in arr_list:
		r = solve(a, b)
		print(r)
main()


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	pos = [0] * (2 * n + 1)
	for i in range(n):
		pos[A[i]] = i
		pos[B[i]] = i
	l = ans = float('inf')
	for i in range(2 * n, 0, -1):
		if i % 2:
			ans = min(ans, l + pos[i])
		else:
			l = min(l, pos[i])
	return ans
for _ in range(int(input())):
	print(solve())


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	(*a,) = map(int, input().split())
	(*b,) = map(int, input().split())
	A = [0] * (2 * n + 3)
	B = [0] * (2 * n + 3)
	for i in range(n):
		A[a[i]] = i
		B[b[i]] = i
	r = 10 * n
	c = r
	for j in range(2 * n - 1, 0, -2):
		c = min(c, B[j + 1])
		r = min(r, A[j] + c)
	print(r)
for i in range(int(input())):
	solve()


def solve(n, a, b):
	list_of_indexes = [0] * (2 * n + 1)
	for (i, el) in enumerate(a):
		list_of_indexes[el] = i
	for (i, el) in enumerate(b):
		list_of_indexes[el] = i
	best_choice_from_b = 2 * n
	answer = 2 * n
	for i in range(2 * n - 1, 0, -2):
		best_choice_from_b = min(best_choice_from_b, list_of_indexes[i + 1])
		answer = min(answer, list_of_indexes[i] + best_choice_from_b)
	return answer
test_count = int(input())
output = list()
for i in range(test_count):
	n = int(input())
	a = input().split(' ')
	a = list(map(int, a))
	b = input().split(' ')
	b = list(map(int, b))
	output.append(solve(n, a, b))
for i in output:
	print(i)


n = int(input())
ans = []
for k in range(n):
	n2 = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	index = {}
	j = 1
	for i in range(n2):
		while j < b[i]:
			index[j] = i
			j += 2
	temp = 100000000
	for i in range(n2):
		temp = min(temp, i + index[a[i]])
	ans.append(temp)
for i in ans:
	print(i)


from sys import stdin
ip = stdin.readline
for _ in range(int(ip())):
	n = int(ip())
	a = list(map(int, ip().split()))
	b = list(map(int, ip().split()))
	idx = [0] * (2 * n + 1)
	for (i, c) in enumerate(zip(a, b)):
		(x, y) = c
		idx[x] = idx[y] = i
	ans = cont = float('inf')
	for i in range(2 * n - 1, 0, -2):
		cont = min(cont, idx[i + 1])
		ans = min(ans, cont + idx[i])
	print(ans)


from sys import stdin
for _ in range(int(stdin.readline())):
	n = int(stdin.readline())
	odd = list(map(int, stdin.readline().split()))
	even = list(map(int, stdin.readline().split()))
	d = {}
	m = 1
	ans = 100000000
	if odd[0] < even[0]:
		ans = 0
	for i in range(n):
		if even[i] > m:
			for j in range(m, even[i], 2):
				if j not in d:
					d[j] = i
			m = even[i] + 1
	for j in range(n):
		ans = min(ans, j + d[odd[j]])
	print(ans)


def sol():
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	ktore = n * [0]
	for i in range(n):
		ktore[(b[i] - 1) // 2] = i
	ans = n * [0]
	ans[n - 1] = ktore[n - 1]
	for i in range(n - 2, -1, -1):
		ans[i] = min(ans[i + 1], ktore[i])
	wyn = 10 ** 9
	for i in range(n):
		wyn = min(wyn, i + ans[a[i] // 2])
	print(wyn)

def main():
	for i in range(int(input())):
		sol()
main()


import sys
input = lambda : sys.stdin.readline()[:-1]
ni = lambda : int(input())
na = lambda : list(map(int, input().split()))
sys.setrecursionlimit(10 ** 7)
yes = lambda : print('yes')
Yes = lambda : print('Yes')
YES = lambda : print('YES')
no = lambda : print('no')
No = lambda : print('No')
NO = lambda : print('NO')
t = ni()
for _ in range(t):
	n = ni()
	a = na()
	b = na()
	bb = [0]
	for i in range(n):
		bb.append(max(bb[-1], b[i]))
	ans = n
	j = n
	for i in range(n):
		while j >= 0 and a[i] < bb[j]:
			j -= 1
		ans = min(ans, i + j)
	print(ans)


def solve():
	t = int(input())
	for _ in range(t):
		solve_one()

def solve_one():
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	assert len(a) == len(b)
	assert len(a) == n
	price = [0] * n
	for (i, ai) in enumerate(a):
		price[ai // 2] = i
	cur_min_price = price[0]
	for (i, p) in enumerate(price[:]):
		if p < cur_min_price:
			cur_min_price = p
		else:
			price[i] = cur_min_price
	min_price = n
	for (i, bi) in enumerate(b):
		bi_price = i + price[bi // 2 - 1]
		min_price = min(min_price, bi_price)
	print(min_price)
solve()


def func(alist, blist, n):
	tmp_ans = 2 * n
	clist = [0] * n
	for i in range(n):
		clist[alist[i] // 2] = i
	j = 0
	for i in range(n):
		while j < n and blist[j] < 2 * i + 1:
			j += 1
		if blist[j] > 2 * i + 1:
			tmp_ans = min(tmp_ans, clist[i] + j)
	return tmp_ans
t = int(input())
for i in range(t):
	n = int(input())
	alist = [int(x) for x in input().split()]
	blist = [int(x) for x in input().split()]
	print(func(alist, blist, n))


for _ in range(int(input())):
	n = int(input())
	odd = list(map(int, input().split()))
	even = list(map(int, input().split()))
	idx = {}
	j = 1
	for i in range(n):
		while j < even[i]:
			idx[j] = i
			j += 2
	ans = float('inf')
	for i in range(n):
		ans = min(ans, i + idx[odd[i]])
	print(ans)


def solution():
	t = int(input())
	for _ in range(t):
		n = int(input())
		a = list(map(int, input().split()))
		b = list(map(int, input().split()))
		b_idx = 0
		for _ in range(n):
			if a[0] > b[b_idx]:
				b_idx += 1
			else:
				break
		res = b_idx
		b_ascending = [(0, b[0])]
		for i in range(1, b_idx + 1):
			if b[i] > b_ascending[-1][1]:
				b_ascending.append((i, b[i]))
		last_from_a = a[0]
		idx = len(b_ascending)
		for i in range(1, n):
			if a[i] < last_from_a:
				while idx != 0 and b_ascending[idx - 1][1] > a[i]:
					idx -= 1
				last_from_a = a[i]
				res = min(res, i + b_ascending[idx][0])
		print(res)
solution()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = [0] * n
	ans = n
	for i in range(n):
		c[a[i] // 2] = i
	for i in range(1, n):
		c[i] = min(c[i], c[i - 1])
	for i in range(n):
		ans = min(ans, i + c[b[i] // 2 - 1])
	print(ans)


from collections import deque
import heapq
from math import sqrt
import operator
from operator import itemgetter
import sys
import copy
inf_var = 0
if inf_var == 1:
	inf = open('input.txt', 'r')
else:
	inf = sys.stdin
input = inf.readline

def read_one_int():
	return int(input().rstrip('\n'))

def read_one_float():
	return float(input().rstrip('\n'))

def read_list_of_ints():
	res = [int(val) for val in input().rstrip('\n').split(' ')]
	return res

def read_str():
	return input().rstrip()

def calc_min_mov(n, odd_elements, even_elements, q):
	res = 2 * n
	odd_to_ind = {}
	for (i, el) in enumerate(odd_elements):
		odd_to_ind[el] = i
	left_smaller = {}
	for i in range(2, 2 * n + 1, 2):
		heapq.heappush(q, odd_to_ind[i - 1])
		left_smaller[i] = q[0]
	for (i, el) in enumerate(even_elements):
		cur_res = left_smaller[el] + i
		res = min(res, cur_res)
		if res == 0:
			break
	print(res)

def main():
	tests = read_one_int()
	for _ in range(tests):
		n = read_one_int()
		odd_elements = read_list_of_ints()
		even_elements = read_list_of_ints()
		q = []
		heapq.heapify(q)
		calc_min_mov(n, odd_elements, even_elements, q)
main()


def calculate_min_amount_of_operations(a, b, array_length):
	indexes = [None for _ in range(array_length * 2)]
	for i in range(array_length):
		indexes[a[i] - 1] = i
	for i in range(array_length):
		indexes[b[i] - 1] = i
	min_amount_of_operations = 2 * array_length
	min_b_index = array_length
	for i in range(array_length * 2 - 1, 0, -2):
		min_b_index = min(min_b_index, indexes[i])
		min_amount_of_operations = min(min_amount_of_operations, min_b_index + indexes[i - 1])
	return min_amount_of_operations
tests_amount = int(input())
for _ in range(tests_amount):
	array_length = int(input())
	array_a = [int(element) for element in input().split(' ')]
	array_b = [int(element) for element in input().split(' ')]
	print(calculate_min_amount_of_operations(array_a, array_b, array_length))


import sys
for k in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))[:n]
	b = list(map(int, input().split()))[:n]
	p = {}
	j = 1
	for i in range(n):
		while j < b[i]:
			p[j] = i
			j += 2
	ans = sys.maxsize
	for i in range(n):
		ans = min(ans, i + p[a[i]])
	print(ans)


from sys import stdin
input = stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	d = {}
	for i in range(len(a)):
		d[a[i]] = i
	prev = float('-inf')
	ans = float('inf')
	for i in range(n):
		if b[i] > prev:
			for j in range(max(0, prev) + 1, b[i], 2):
				ans = min(ans, d.get(j) + i)
			prev = b[i]
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	ar = [0] * n
	for j in range(n):
		x = (a[j] + 1) // 2
		ar[x - 1] = j
	m = ar[0]
	for j in range(n):
		if ar[j] > m:
			ar[j] = m
		else:
			m = ar[j]
	m = 3 * n
	for j in range(n):
		x = b[j] // 2
		m = min(m, j + ar[x - 1])
	print(m)


t = int(input())
for _ in range(t):
	n = int(input())
	arrA = [int(x) for x in input().split(' ')]
	arrB = [int(x) for x in input().split(' ')]
	indexmap = {arrA[x]: x for x in range(n)}
	lessOrEqual = {}
	lessOrEqual[1] = indexmap[1]
	for i in range(3, 2 * n, 2):
		lessOrEqual[i] = min(indexmap[i], lessOrEqual[i - 2])
	mincost = lessOrEqual[arrB[0] - 1]
	for i in range(1, n):
		if arrB[i] > arrB[0] and i < mincost:
			evenshift = i
			oddshift = lessOrEqual[arrB[i] - 1]
			mincost = min(mincost, oddshift + evenshift)
	print(mincost)


import sys
input = lambda : sys.stdin.readline().rstrip()
from bisect import bisect_left as bisect

def solve():
	n = int(input())
	A = list(map(int, input().split()))
	B = list(map(int, input().split()))
	ans = 2 * n
	minA = [2 * n for _ in range(n)]
	maxB = [0 for _ in range(n)]
	minA[0] = A[0]
	maxB[0] = B[0]
	for i in range(1, n):
		minA[i] = min(minA[i - 1], A[i])
		maxB[i] = max(maxB[i - 1], B[i])
	for i in range(n):
		j = bisect(maxB, minA[i])
		ans = min(ans, i + j)
	print(ans)
T = int(input())
for i in range(1, T + 1):
	solve()


for i in range(int(input())):
	n = int(input())
	d1 = {}
	d2 = {}
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	for i in range(n):
		d1[a[i]] = i
	d2[1] = d1[1]
	for i in range(3, 2 * n, 2):
		d2[i] = min(d2[i - 2], d1[i])
	ans = float('inf')
	for i in range(n):
		ans = min(ans, i + d2[b[i] - 1])
	print(ans)


import sys
import math
from bisect import bisect_right as br
from statistics import mode
from itertools import combinations as cb

def int_arr():
	return list(map(int, sys.stdin.readline().strip().split()))

def str_arr():
	return list(map(str, sys.stdin.readline().strip().split()))

def input():
	return sys.stdin.readline().strip()
for _ in range(int(input())):
	n = int(input())
	a = int_arr()
	b = int_arr()
	step = [0 for i in range(n * 2)]
	for i in range(n):
		step[a[i] - 1] = i
	mn = float('inf')
	for i in range(0, n * 2, 2):
		mn = min(mn, step[i])
		step[i] = mn
	ans = float('inf')
	for j in range(n):
		ans = min(ans, j + step[b[j] - 2])
	print(ans)


t = int(input())
a = [0 for i in range(0, 100010)]
b = [0 for i in range(0, 100010)]
while t > 0:
	t -= 1
	n = int(input())
	for i in range(1, n + 1):
		a[i] = 0
		b[i] = 0
	temp = input().split(' ')
	for i in range(1, n + 1):
		a[int(temp[i - 1]) // 2 + 1] = i
	temp = input().split(' ')
	for i in range(1, n + 1):
		b[int(temp[i - 1]) // 2] = i
	min = 1000000
	for i in range(n - 1, 0, -1):
		if b[i] > b[i + 1]:
			b[i] = b[i + 1]
	for i in range(1, n + 1):
		sum = a[i] + b[i]
		if min > sum:
			min = sum
	print(min - 2)


def solve():
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	sorted_by_values = [None for _ in range(2 * n)]
	for i in range(n):
		sorted_by_values[a[i] - 1] = i
		sorted_by_values[b[i] - 1] = i
	min_greater_index = sorted_by_values[2 * n - 1]
	min_swaps = 2 * n
	for odd_number in range(2 * n - 1, 0, -2):
		min_greater_index = min(min_greater_index, sorted_by_values[odd_number])
		min_swaps = min(min_swaps, min_greater_index + sorted_by_values[odd_number - 1])
	return min_swaps
t = int(input())
for _ in range(t):
	print(solve())


import math
import heapq
import string
from collections import deque
from bisect import bisect, bisect_left, bisect_right, insort
import sys
input = sys.stdin.readline
S = lambda : input().rstrip()
I = lambda : int(S())
M = lambda : map(int, S().split())
L = lambda : list(M())
H = 1000000000 + 7
for _ in range(I()):
	n = I()
	a = L()
	b = L()
	m = ans = n
	l = [0] * (2 * n + 1)
	for i in range(n):
		l[a[i]] = i
		l[b[i]] = i
	for i in range(2 * n, 0, -1):
		if i % 2 == 0:
			m = min(l[i], m)
		else:
			ans = min(ans, l[i] + m)
	print(ans)


def main():
	t = input()
	t = int(t)
	for i in range(t):
		n = input()
		n = int(n)
		a = input().split()
		b = input().split()
		ans = 2 * n + 5
		position = [0 for i in range(2 * n + 5)]
		for i in range(len(a)):
			x = int(a[i])
			position[x] = i
			y = int(b[i])
			position[y] = i
		l = position[1]
		for i in range(1, 2 * n + 1):
			if i % 2 == 0:
				ans = min(ans, position[i] + l)
			else:
				l = min(l, position[i])
		print(ans)
main()


import sys

def swaps(n, a, b):
	a = [int(i) for i in a]
	b = [int(i) for i in b]
	a_pos = sorted(range(len(a)), key=a.__getitem__)
	b_pos = sorted(range(len(b)), key=b.__getitem__)
	res = sys.maxsize
	dis_a = sys.maxsize
	for i in range(n):
		dis_a = min(dis_a, a_pos[i])
		res = min(res, dis_a + b_pos[i])
	return res
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(input().split())
	b = list(input().split())
	print(swaps(n, a, b))


for k in range(int(input())):
	len_num = int(input())
	a_num = [int(n) for n in input().split()]
	b_num = [int(n) for n in input().split()]
	c = [0] * len_num
	for i in range(len_num):
		c[a_num[i] // 2] = i
	for i in range(1, len_num):
		c[i] = min(c[i], c[i - 1])
	count = len_num
	for i in range(len_num):
		count = min(count, i + c[b_num[i] // 2 - 1])
	print(count)


T = int(input())
for _ in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	indexes = [0] * (2 * n + 1)
	min_b_pos = 2 * n
	answer = 2 * n
	for i in range(n):
		indexes[a[i]] = i
		indexes[b[i]] = i
	for j in range(len(indexes) - 2, 0, -2):
		min_b_pos = min(min_b_pos, indexes[j + 1])
		answer = min(answer, min_b_pos + indexes[j])
	print(answer)


def int_input():
	a = int(input())
	return a

def int_list_input():
	a = list(map(int, input().split()))
	return a

def solve():
	n = int(input())
	a = int_list_input()
	b = int_list_input()
	for i in range(n):
		if a[i] > b[i]:
			break
		elif a[i] < b[i]:
			print(0)
			return
	ans = float('inf')
	d = [0 for _ in range(2 * n)]
	for i in range(n):
		d[a[i] - 1] = i
		d[b[i] - 1] = i
	for i in range(2 * n - 3, 0, -2):
		d[i] = min(d[i + 2], d[i])
	for i in range(0, 2 * n, 2):
		j = d[i + 1]
		ans = min(ans, d[i] + j)
	print(ans)
for _ in range(int(input())):
	solve()


T = int(input())
for _ in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	pos = dict()
	for (i, x) in enumerate(a):
		pos[x] = i
	for i in range(3, 2 * n, 2):
		pos[i] = min(pos[i - 2], pos[i])
	ans = float('inf')
	for i in range(n):
		ans = min(ans, i + pos[b[i] - 1])
	print(ans)


import math, bisect, heapq, random, sys, itertools
sys.setrecursionlimit(10 ** 5)
ints = lambda : list(map(int, input().split()))
alpha = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'
p = 10 ** 9 + 7
for t in range(int(input())):
	n = int(input())
	a = ints()
	b = ints()
	store = {}
	for i in range(n):
		store[a[i]] = i
	dp = []
	minn = p
	for i in range(1, 2 * n, 2):
		minn = min(minn, store[i])
		dp.append(minn)
	ans = p
	for i in range(n):
		moves = i + dp[b[i] // 2 - 1]
		ans = min(moves, ans)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	limit = 2 * n + 1
	a = (*map(int, input().split()),)
	b = (*map(int, input().split()),)
	d = {}
	for i in range(n):
		for even in range(a[i] + 1, limit, 2):
			if even in d:
				break
			d[even] = i
	ans = float('inf')
	for i in range(n):
		swaps = i + d[b[i]]
		ans = min(swaps, ans)
	print(ans)


import sys
from collections import deque
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = {}
	d = {}
	for i in range(n):
		c[a[i]] = i
		d[b[i]] = i
	temp = n
	result = 2 * n
	k = 1
	while k <= n:
		temp = min(temp, c[2 * k - 1])
		result = min(result, d[2 * k] + temp)
		k += 1
	print(result)


t = int(input())
for _ in range(t):
	n = int(input())
	odd = list(map(int, input().split()))
	even = list(map(int, input().split()))
	min_steps = [0] * (n + 1)
	for (id, i) in enumerate(even):
		min_steps[i // 2] = id
	for i in range(2 * n - 2, 0, -2):
		min_steps[i // 2] = min(min_steps[i // 2], min_steps[(i + 2) // 2])
	mn = 4 * n
	mn_value = odd[0]
	for (id, i) in enumerate(odd):
		if i <= mn_value:
			mn = min(mn, id + min_steps[(i + 1) // 2])
			i = mn_value
	print(mn)


n = int(input())
while n:
	n -= 1
	f = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	ev = [0] * f
	for i in range(f):
		ev[b[i] // 2 - 1] = i
	mi = 100000000000
	for i in reversed(range(f)):
		ev[i] = min(mi, ev[i])
		mi = min(mi, ev[i])
	mi = 1000000000000
	for i in range(f):
		mi = min(i + ev[(a[i] - 1) // 2], mi)
	print(mi)


def bs(val):
	(l, r) = (0, n - 1)
	while l <= r:
		mid = l + (r - l) // 2
		if b[mid] > val:
			r = mid - 1
		else:
			l = mid + 1
	return b[l]
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	ans = float('inf')
	pos = {}
	for j in range(n):
		pos[b[j]] = j
	minind = {}
	cind = float('inf')
	for j in range(2 * n, 1, -2):
		cind = min(cind, pos[j])
		minind[j] = cind
	for j in range(n):
		ele = a[j] + 1
		ans = min(ans, j + minind[ele])
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	astr = input().split()
	a = [(int(astr[i]), i) for i in range(len(astr))]
	b = list(map(int, input().split()))
	c = 999999999
	aa = sorted(a, key=lambda x: x[0])
	for i in range(len(b)):
		if i > 1:
			j = j
		else:
			j = 0
		while aa[i][0] > b[j]:
			j += 1
		c = min(c, j + aa[i][1])
	print(c)


T = int(input())
for haha in range(T):
	n = int(input())
	a = []
	b = []
	pos = [None] * (2 * n + 5)
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	for _ in range(n):
		pos[a[_]] = _
	for _ in range(n):
		pos[b[_]] = _
	res = 1000000
	mi = 1000000
	i = 2 * n - 1
	while i >= 1:
		mi = min(mi, pos[i + 1])
		res = min(res, mi + pos[i])
		i -= 2
	print(res)


from sys import *
t = int(input())
for i in range(t):
	n = int(input())
	numList = [0] * (2 * n + 1)
	recList = numList.copy()
	a = list(map(int, input().split()))
	for i in range(len(a)):
		numList[a[i]] = i
	b = list(map(int, input().split()))
	for i in range(len(b)):
		numList[b[i]] = i
	minNum = float('inf')
	for i in range(1, len(numList), 2):
		minNum = min(minNum, numList[i])
		recList[i] = minNum
	ans = float('inf')
	for i in range(2, len(numList), 2):
		ans = min(ans, numList[i] + recList[i - 1])
	print(ans)


t = input()
for k in range(int(t)):
	z = int(input())
	n = list(map(int, input().split()))
	m = list(map(int, input().split()))
	c = [0] * z
	for i in range(z):
		c[n[i] // 2] = i
	for i in range(1, z):
		c[i] = min(c[i], c[i - 1])
	for i in range(z):
		c[i] = c[int(m[i] / 2) - 1] + i
	mini = min(c)
	print(mini)


t = int(input())
while t > 0:
	n = int(input())
	a = [int(i) for i in input().split()]
	b = [int(i) for i in input().split()]
	index = [0 for i in range(n + 1)]
	for i in range(n):
		index[a[i] // 2] = i
	c = 0
	ans = n
	for i in range(1, n):
		index[i] = min(index[i - 1], index[i])
	for i in range(n):
		ans = min(index[b[i] // 2 - 1] + i, ans)
		c += 1
	print(ans)
	t -= 1


from collections import Counter

def solve():
	n = int(input())
	A = [int(char) for char in input().split()]
	B = [int(char) for char in input().split()]
	ans = n - 1
	for (i, a) in enumerate(A):
		for (j, b) in enumerate(B):
			if a < b:
				ans = min(ans, i + j)
	print(ans)

def solve2():
	n = int(input())
	A = [int(char) for char in input().split()]
	B = [int(char) for char in input().split()]
	A_pos = {a: i for (i, a) in enumerate(A)}
	Bs = sorted([(b, i) for (i, b) in enumerate(B)])
	Bmin = [i for (b, i) in Bs]
	for i in range(n - 2, -1, -1):
		Bmin[i] = min(Bmin[i + 1], Bmin[i])
	ans = 2 * (n - 1)
	for i in range(n):
		odd_num = 2 * i + 1
		ans = min(ans, A_pos[odd_num] + Bmin[i])
	return ans
for _ in range(int(input())):
	print(solve2())


from collections import deque

def min_to_the_right(n, sorted_array):
	queue = deque([])
	min_moves = [0 for x in range(n)]
	for i in range(n - 1, -1, -1):
		while len(queue) > 0 and queue[0] > sorted_array[i]:
			queue.popleft()
		queue.appendleft(sorted_array[i])
		min_moves[i] = queue[-1]
	return min_moves

def solve(n, a, b):
	sorted_array = [0 for x in range(n)]
	for i in range(n):
		sorted_array[b[i] // 2 - 1] = i
	min_moves = min_to_the_right(n, sorted_array)
	final_ans = float('inf')
	for i in range(n):
		first = a[i]
		second = b[i]
		current = i
		just_greater = first + 1
		no_of_moves = min_moves[just_greater // 2 - 1]
		current += no_of_moves
		final_ans = min(final_ans, current)
	return final_ans
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = [int(x) for x in input().split()]
	print(solve(n, a, b))


for ii in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	b = [int(i) for i in input().split()]
	even = 10 ** 9
	ans = 10 ** 9
	e = {}
	for i in range(n):
		e[a[i]] = i
		e[b[i]] = i
	for i in range(2 * n, 0, -1):
		even = min(even, e[i]) if i % 2 == 0 else even
		ans = min(ans, e[i] + even) if i % 2 != 0 else ans
	print(ans)


t = int(input())
for case in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	d = {}
	for i in range(n):
		d[a[i]] = i
		d[b[i]] = i
	ans = 2 * n
	a.sort()
	b.sort()
	mini = [0] * n
	mini[n - 1] = d[b[n - 1]]
	for i in range(n - 2, -1, -1):
		mini[i] = min(mini[i + 1], d[b[i]])
	for i in range(n):
		ans = min(ans, d[a[i]] + mini[i])
	print(ans)


import sys
sys.setrecursionlimit(10 ** 6)
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	m = 10 ** 9
	ans = 10 ** 9
	c = [0] * n
	d = [0] * n
	for i in range(n):
		c[(a[i] - 1) // 2] = i
		d[(b[i] - 1) // 2] = i
	for i in range(n - 1, -1, -1):
		d[i] = min(m, d[i])
		m = d[i]
		ans = min(ans, m + c[i])
	print(ans)


tst = int(input())
for _ in range(tst):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	d = {}
	for i in range(n):
		d[arr[i]] = i
	arr = list(map(int, input().split(' ')))
	for i in range(n):
		d[arr[i]] = i
	l = float('inf')
	answer = float('inf')
	for i in range(2 * n, 0, -1):
		if i % 2 == 0:
			l = min(l, d[i])
		else:
			answer = min(answer, l + d[i])
	print(answer)


T = int(input())

def swapPlaces(arrOdd, arrEven):
	h = {}
	for (i, a) in enumerate(arrOdd):
		h[a] = i
	for (i, b) in enumerate(arrEven):
		h[b] = i
	arrOdd.sort(reverse=True)
	arrEven.sort(reverse=True)
	suffixMin = []
	c = float('inf')
	for (i, a) in enumerate(arrEven):
		m = min(c, h[a])
		suffixMin.append(m)
		c = m
	minDist = float('inf')
	for (i, a) in enumerate(arrOdd):
		dist = h[a] + suffixMin[i]
		minDist = min(minDist, dist)
	return minDist
for t in range(T):
	n = int(input())
	a = [int(c) for c in input().split()]
	b = [int(c) for c in input().split()]
	print(swapPlaces(a, b))


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	swap_a = {}
	swap_b = {}
	for i in range(n):
		swap_a[a[i]] = i
		swap_b[b[i]] = i
	b.sort()
	mini = 10 ** 8
	suff = []
	for i in range(n - 1, -1, -1):
		mini = min(mini, swap_b[b[i]])
		suff.append(mini)
	ans = 10 ** 15
	suff.reverse()
	for i in range(n):
		ans = min(ans, swap_a[a[i]] + suff[a[i] // 2])
	print(ans)


for i in range(int(input())):
	n = int(input())
	odd = list(map(int, input().split()))
	eve = list(map(int, input().split()))
	indices = [-1 for j in range(n + 1)]
	for j in range(n):
		indices[eve[j] // 2] = j
	prev = 2 * n
	for j in range(n, 0, -1):
		prev = min(indices[j], prev)
		indices[j] = prev
	mi = 2 * n - 1
	for j in range(n):
		steps = j + indices[odd[j] // 2 + 1]
		mi = min(mi, steps)
	print(mi)


t = int(input())
while t:
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	req_a = a[0]
	req_b = b[0]
	if req_a < req_b:
		print(0)
	else:
		swaps = [0] * (2 * n + 1)
		for (i, val) in enumerate(b):
			swaps[val] = i
		for i in range(2 * n - 2, -1, -1):
			swaps[i] = min(swaps[i], swaps[i + 2])
		ans = n
		for i in range(n):
			ans = min(ans, i + swaps[a[i] + 1])
		print(ans)
	t -= 1


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(j) for j in input().split()]
	b = [int(j) for j in input().split()]
	mp = [10 ** 7] * (2 * n + 1)
	for i in range(n):
		mp[b[i]] = i
	minmp = [0] * (2 * n + 1)
	minmp[2 * n] = mp[2 * n]
	for i in range(2 * n - 1, -1, -1):
		minmp[i] = min(minmp[i + 1], mp[i])
	ans = 10 ** 10
	for i in range(n):
		ans = min(ans, i + minmp[a[i] + 1])
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	c = a[:]
	d = b[:]
	for i in range(1, n):
		c[i] = min(c[i - 1], a[i])
		d[i] = max(d[i - 1], b[i])
	ans = 2 * (n - 1)
	x = 0
	y = 0
	for i in range(n):
		if c[i] < d[0]:
			ans = min(ans, i)
			x = i
			y = 0
			break
	else:
		for j in range(n):
			if c[i] < d[j]:
				ans = min(ans, i + j)
				x = i
				y = j
				break
	while x > 0:
		x -= 1
		while c[x] >= d[y] and y < n - 1:
			y += 1
		if c[x] < d[y]:
			ans = min(ans, x + y)
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	d = {}
	for i in range(len(a)):
		d[a[i]] = i
	prev = float('-inf')
	ans = float('inf')
	for i in range(n):
		if b[i] > prev:
			for j in range(max(0, prev) + 1, b[i], 2):
				ans = min(ans, d.get(j) + i)
			prev = b[i]
	print(ans)


t = int(input())
for y in range(t):
	n = int(input())
	a = input().split()
	b = input().split()
	a = [int(x) for x in a]
	b = [int(x) for x in b]
	k = [-1] * n
	m = [-1] * n
	val1 = max(a) + 1
	val2 = -1
	for i in range(n):
		val1 = min(val1, a[i])
		k[i] = val1
		val2 = max(val2, b[i])
		m[i] = val2
	c1 = n - 1
	c2 = 0
	l = []
	ans = 2 * n
	while c1 >= 0:
		if k[c1] < m[c2]:
			l.append((k[c1], m[c2]))
			ans = min(ans, c1 + c2)
			c1 -= 1
		else:
			c2 += 1
	print(ans)


t = int(input())
while t > 0:
	n = int(input())
	t = t - 1
	a = list(map(int, input().split(' ')))
	b = list(map(int, input().split(' ')))
	gt = [0 for i in range(0, 2 * n + 2)]
	idx = [0 for i in range(0, 2 * n + 2)]
	gt[2 * n + 1] = 300000
	res = 300000
	for i in range(0, n):
		idx[b[i]] = i
	for i in range(2 * n - 1, 0, -2):
		gt[i] = min(gt[i + 2], idx[i + 1])
	for i in range(0, n):
		res = min(res, i + gt[a[i]])
	print(res)


t = int(input())
for y in range(t):
	n = int(input())
	a = input().split()
	b = input().split()
	a = [int(x) for x in a]
	b = [int(x) for x in b]
	c = [-1] * n
	d = [-1] * n
	val1 = max(a) + 1
	val2 = -1
	for i in range(n):
		val1 = min(val1, a[i])
		c[i] = val1
		val2 = max(val2, b[i])
		d[i] = val2
	p1 = n - 1
	p2 = 0
	l = []
	ans = 2 * n
	while p1 >= 0:
		if c[p1] < d[p2]:
			l.append((c[p1], d[p2]))
			ans = min(ans, p1 + p2)
			p1 -= 1
		else:
			p2 += 1
	print(ans)


import sys

def mgc(a, b, n):
	(first, second) = ([], [])
	if a[0] < b[0]:
		return 0
	for i in range(n):
		first.append([a[i], i])
		second.append([b[i], i])
	first.sort()
	second.sort()
	mini = []
	x = second[-1][1]
	for i in range(n - 1, -1, -1):
		x = min(x, second[i][1])
		mini.append(x)
	mini = mini[::-1]
	ans = sys.maxsize
	for i in range(n):
		ans = min(ans, first[i][1] + mini[i])
	return ans
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	print(mgc(a, b, n))


for _ in range(int(input().strip())):
	n = int(input().strip())
	a = list(map(int, input().strip().split()))
	b = list(map(int, input().strip().split()))
	arr = [10 ** 6] * (2 * n)
	for i in range(n):
		arr[a[i] - 1] = i
	an = 10 ** 6
	for i in range(1, 2 * n):
		arr[i] = min(arr[i], arr[i - 1])
	for i in range(n):
		an = min(arr[b[i] - 1] + i, an)
	print(an)


t = int(input())
for k in range(t):
	n = int(input())
	a = []
	b = []
	inp = input().split()
	for i in inp:
		a.append(int(i))
	inp = input().split()
	for i in inp:
		b.append(int(i))
	d = [0]
	for i in range(len(b)):
		d.append(max(d[-1], b[i]))
	j = n
	ans = 10 ** 9
	for i in range(n):
		while j >= 0 and a[i] < d[j]:
			j -= 1
		ans = min(ans, i + j)
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	list_odd = list(map(int, input().split()))
	list_even = list(map(int, input().split()))
	if n == 1:
		print(0)
	else:
		(list1, list2) = ([], [])
		for i in range(n):
			list1.append(-1)
			list2.append(-1)
		counter = 0
		for i in list_odd:
			place = int(0.5 * (i - 1))
			list1[place] = counter
			counter += 1
		counter = 0
		for i in list_even:
			place = int(0.5 * i - 1)
			list2[place] = counter
			counter += 1
		index = 0
		list1_modified = list1[:]
		while True:
			if list1_modified[index + 1] > list1_modified[index]:
				list1_modified[index + 1] = list1_modified[index]
			index += 1
			if index == n - 1:
				break
		index = -1
		list2_modified = list2[:]
		while True:
			if list2_modified[index - 1] > list2_modified[index]:
				list2_modified[index - 1] = list2_modified[index]
			index -= 1
			if index == -n:
				break
		list_final = []
		for i in range(n):
			list_final.append(list1_modified[i] + list2_modified[i])
		step = min(list_final)
		print(step)


t = int(input())
for i in range(t):
	n = int(input())
	lsta = list(map(int, input().split()))
	lstb = list(map(int, input().split()))
	dic = {}
	la = []
	lb = []
	for d in range(n):
		dic[lsta[d]] = d
		dic[lstb[d]] = d
		la.append([lsta[d], d])
		lb.append([lstb[d], d])
	c = 0
	for k in range(2, 2 * n + 1, 2):
		if k == 2:
			ele = 1
			c = dic[2] + dic[1]
		else:
			if dic[k - 1] < dic[ele]:
				ele = k - 1
			c1 = dic[ele] + dic[k]
			c = min(c1, c)
	print(c)


import math
for m in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	dict = {}
	c = []
	for i in range(len(a)):
		c.append([a[i], i])
	c.sort()
	min1 = math.inf
	for z in range(len(a)):
		min1 = min((c[z][1], min1))
		dict[c[z][0] + 1] = min1
	q = math.inf
	for k in range(len(b)):
		q = min(abs(k + dict[b[k]]), q)
	print(q)


from collections import deque, Counter
from collections import defaultdict as dfd
from bisect import bisect, bisect_left
from math import sqrt, gcd, ceil, factorial, log2
from heapq import heapify, heappush, heappop
MOD = 10 ** 9 + 7
inf = float('inf')
ans_ = []

def nin():
	return int(input())

def ninf():
	return int(file.readline())

def st():
	return input().strip()

def stf():
	return file.readline().strip()

def read():
	return list(map(int, input().strip().split()))

def readf():
	return list(map(int, file.readline().strip().split()))

def readfl():
	return list(map(float, input().strip().split()))

def readffl():
	return list(map(float, file.readline().strip().split()))

def solve():
	for _ in range(nin()):
		n = nin()
		a = read()
		b = read()
		a = sorted([(a[i], i) for i in range(n)])
		b = sorted([(b[i], i) for i in range(n)])
		ans = 10 ** 9
		mini = 10 ** 9
		for i in range(n):
			mini = min(mini, a[i][1])
			ans = min(ans, mini + b[i][1])
		ans_.append(ans)
solve()
for i in ans_:
	print(i)


for _ in range(int(input())):
	n = int(input())
	a = [[x, i] for (i, x) in enumerate(list(map(int, input().split(' '))))]
	b = [[x, i] for (i, x) in enumerate(list(map(int, input().split(' '))))]
	a.sort(key=lambda x: x[0])
	b.sort(key=lambda x: x[0])
	out = float('inf')
	mn = float('inf')
	for i in range(len(a)):
		mn = min(mn, a[i][1])
		out = min(out, b[i][1] + mn)
	print(out)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	brr = list(map(int, input().split()))
	d = []
	e = []
	for i in range(n):
		d.append((arr[i], i))
		e.append((brr[i], i))
	d.sort()
	e.sort()
	m = [e[-1][1]]
	for el in e[-2::-1]:
		if el[1] < m[-1]:
			m.append(el[1])
		else:
			m.append(m[-1])
	m = m[::-1]
	ans = float('inf')
	i = 0
	for (a, b) in d:
		ans = min(ans, b + m[i])
		i += 1
	print(ans)


for _ in range(int(input())):
	ewr = input()
	a = [int(i) for i in input().split()]
	b = [int(i) for i in input().split()]
	if a[0] < b[0]:
		print(0)
	else:
		c = []
		d = []
		st = dict()
		for i in range(len(a)):
			st[a[i]] = i
			c.append([a[i], i])
			d.append([b[i], i])
		c = sorted(c, key=lambda x: x[0])
		c = sorted(a)
		d = sorted(d, key=lambda x: x[0])
		i = len(d) - 1
		mini = d[i][-1]
		arr = []
		while i >= 0:
			arr.append(mini)
			i -= 1
			mini = min(mini, d[i][-1])
		arr = arr[::-1]
		ans = 10 ** 9
		for i in range(len(c)):
			ans = min(ans, st[c[i]] + arr[i])
		print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	firstleqa = {}
	for i in range(n):
		j = a[i]
		while j <= 2 * n and j not in firstleqa:
			firstleqa[j] = i
			j += 1
	firstgeqb = {}
	firstgeqb[2 * n - 1] = int(1000000000.0)
	for i in range(n):
		j = b[i]
		while j >= 0 and j not in firstgeqb:
			firstgeqb[j] = i
			j -= 1
	ans = int(1000000000.0)
	for i in range(n):
		ans = min(ans, i + firstleqa[b[i]])
		ans = min(ans, i + firstgeqb[a[i]])
	print(ans)


for _ in range(int(input())):
	n = int(input())
	odd = list(map(int, input().split()))
	even = list(map(int, input().split()))
	odd = [[odd[i], i] for i in range(n)]
	even = [[even[i], i] for i in range(n)]
	odd.sort()
	even.sort()
	ans = n
	mini = 10000000
	for i in range(n - 1, -1, -1):
		mini = min(even[i][1], mini)
		ans = min(mini + odd[i][1], ans)
	print(ans)


def getarray():
	return list(map(int, input().split()))

def getints():
	return map(int, input().split())

def getint():
	return int(input())

def solve():
	n = getint()
	a = getarray()
	b = getarray()
	(arr, brr) = ([], [])
	for i in range(n):
		arr.append([a[i], i])
		brr.append([b[i], i])
	arr.sort()
	brr.sort()
	postarr = [float('inf')] * n
	postbrr = [float('inf')] * n
	postbrr[-1] = brr[-1][1]
	for i in range(n - 2, -1, -1):
		postbrr[i] = min(brr[i][1], postbrr[i + 1])
	ans = float('inf')
	for i in range(n):
		ans = min(ans, arr[i][1] + postbrr[i])
	print(ans)
for t in range(getint()):
	solve()


import sys

def func():
	n = int(input())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	ma = []
	mb = []
	for i in range(n):
		ma.append([a[i], i])
		mb.append([b[i], i])
	ma.sort()
	mb.sort()
	lia = [0 for i in range(n)]
	lia[n - 1] = mb[n - 1][1]
	idx = n - 2
	while idx >= 0:
		lia[idx] = min(lia[idx + 1], mb[idx][1])
		idx -= 1
	mnp = sys.maxsize
	for i in range(n):
		mnp = min(mnp, ma[i][1] + lia[i])
	print(mnp)
t = int(input())
for i in range(t):
	func()


import sys
fast_input = sys.stdin.readline
t = int(fast_input())
while t:
	t -= 1
	n = int(fast_input())
	a = list(map(int, fast_input().split()))
	b = list(map(int, fast_input().split()))
	new = []
	for i in range(n):
		new.append([a[i], i])
		new.append([b[i], i])
	new.sort(reverse=True)
	res = 2 * n
	(x, y) = (n, n)
	for ne in new:
		if ne[0] % 2 == 0:
			x = min(x, ne[1])
		else:
			res = min(res, x + ne[1])
	print(res)