Chef has a permutation P of length 2 \cdot N. He can perform the following operation on P:
Select an index i (1 ≤ i < 2 \cdot N) and swap P_{i} and P_{i + 1}.

Chef would call the permutation P *good*, if the maximum element of the first half of P is less than the minimum element of the second half of P.  
Formally \displaystyle \max_{(1 ≤ i ≤ N)} P_{i} < \min_{(N < i ≤ 2 \cdot N)} P_{i}.

Find the minimum number of operations Chef needs to apply to make P *good*.

Note: A permutation of length N is an array where every integer from 1 to N occurs exactly once.

------ Input Format ------ 

- The first line contains a single integer T — the number of test cases. Then the test cases follow.
- The first line of each test case contains an integer N — half the size of the permutation P.
- The second line of each test case contains 2 \cdot N space-separated integers P_{1}, P_{2}, \dots, P_{2 \cdot N} denoting the permutation P.

------ Output Format ------ 

For each test case, output the minimum number of operations required to make P *good*.

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$1 ≤ N ≤ 10^{5}$
$P$ is a permutation of length $2 \cdot N$
- The sum of $N$ over all test cases won't exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------ 
3
2
3 2 1 4
3
1 2 3 4 5 6
3
6 5 4 3 2 1

----- Sample Output 1 ------ 
2
0
9

----- explanation 1 ------ 
Test case $1$: We can perform the following operations:
- Apply operation at $i = 1$: $[3, 2, 1, 4] \rightarrow [2, 3, 1, 4]$
- Apply operation at $i = 2$: $[2, 3, 1, 4] \rightarrow [2, 1, 3, 4]$

Test case $2$: $P$ is already good.

Difficulty: MEDIUM
Tags: Constructive algorithms

Ad-hoc

Starter code:

Solutions:
zoro = int(input())

def main():
	for i in range(zoro):
		solve()

def solve():
	n = int(input())
	arr = [int(_) for _ in input().split()]
	res = 0
	count = 0
	for x in arr:
		if x <= n:
			res += count
		else:
			count += 1
	print(res)
main()


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = l[:n]
	l2 = l[n:]
	(sum, count) = (0, 0)
	for i in range(n):
		if l1[i] > n:
			count += 1
			sum += abs(n - 1 - i)
		if l2[i] < n + 1:
			sum += i
	print(sum + count)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	knt = 0
	s = 0
	for i in range(n, -1, -1):
		if l[i] <= n:
			if i < n:
				s += i - knt
				knt += 1
	for j in range(n, 2 * n):
		if l[j] <= n:
			s += j - knt
			knt += 1
	print(s)


t = int(input())
for _ in range(t):
	n = int(input())
	p = list(map(int, input().split()))
	(c, m) = (0, 0)
	for i in range(2 * n):
		if p[i] > n:
			p[i] = 1
			m += 1
		else:
			p[i] = 0
			c += m
	print(c)


for i in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	sum1 = 0
	sum2 = 0
	for i in range(n):
		if lst[i] > n:
			sum1 += i
		if lst[i + n] < n + 1:
			sum2 += i + n
	print(sum2 - sum1)


t = int(input())
for _ in range(t):
	n = int(input())
	a = input().split(' ')
	_1 = []
	_0 = []
	ans = 0
	for i in range(2 * n):
		if int(a[i]) <= n:
			a[i] = 0
			if i >= n:
				_0.append(i)
		else:
			a[i] = 1
			if i < n:
				_1.append(i)
	for j in range(len(_0)):
		ans += _0[j] - _1[j]
	print(ans)


t = int(input())
for i in range(t):
	n1 = int(input())
	n = 2 * n1
	l = [int(x) for x in input().split()]
	z = int(n / 2)
	x = 0
	y = 0
	for j in range(0, z):
		if l[j] > n / 2:
			x += j
	for j in range(z, n):
		if l[j] <= n / 2:
			y += j
	print(y - x)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	l1 = []
	for i in range(0, n):
		if l[i] > n:
			l1.append(i)
	l2 = []
	for i in range(n, 2 * n):
		if l[i] <= n:
			l2.append(i)
	res = 0
	for (x, y) in zip(l1, l2):
		res += abs(x - y)
	print(res)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = sorted(a)
	ans = 0
	(i, l, k) = (2 * n - 1, 2 * n - 1, 0)
	while k < n and i > -1:
		if a[i] >= b[n]:
			ans += l - i
			l -= 1
			k += 1
		i -= 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	(min_swap, j) = (0, 0)
	for i in range(2 * n):
		if l[i] <= n:
			min_swap += i - j
			j += 1
	print(min_swap)


for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	ans = 0
	filled = 0
	for i in range(len(p)):
		if p[i] <= n:
			ans += i - filled
			filled += 1
	print(ans)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	k = 0
	ms = 0
	for i in range(2 * n):
		if l[i] <= n:
			ms += i - k
			k += 1
	print(ms)


for tc in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	(count, j) = (0, 0)
	for i in range(2 * n):
		if arr[i] <= n:
			count += i - j
			j += 1
	print(count)


for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	j = 0
	count = 0
	for i in range(2 * n):
		if p[i] > n:
			count += n - i + j
			j += 1
	print(count)


for t in range(int(input())):
	n = int(input())
	num = list(map(int, input().split()))
	a = 0
	itr = n
	for i in range(n):
		ele = num[i]
		if ele > n:
			while num[itr] > n:
				itr += 1
			a += itr - i
			itr += 1
	print(a)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split(' ')))
	j = 0
	s = 0
	for i in range(len(l)):
		if l[i] <= n:
			s = s + (i - j)
			j += 1
	print(s)


T = int(input())
for t in range(T):
	N = int(input())
	P = list(map(int, input().split()))
	j = 0
	ans = 0
	for i in range(2 * N):
		if P[i] <= N:
			ans += i - j
			j += 1
	print(ans)


import sys
input = sys.stdin.readline

def inp():
	return int(input())

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

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

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

def outp(n):
	sys.stdout.write(str(n) + '\n')

def outlt(lst):
	sys.stdout.write(' '.join(map(str, lst)) + '\n')

def outplt(lst):
	sys.stdout.write('\n'.join(map(str, lst)))

def outpltlt(lst):
	sys.stdout.write('\n'.join(map(str, (' '.join(map(str, a)) for a in lst))))
ans = []
for _ in range(inp()):
	(N, A) = (inp(), inlt())
	t = [i for i in range(N, 2 * N) if A[i] <= N]
	ans.append(sum((t.pop(-1) - i for i in range(N) if A[i] > N)))
outplt(ans)


import sys
input = sys.stdin.readline

def inp():
	return int(input())

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

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

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

def outp(n):
	sys.stdout.write(str(n) + '\n')

def outlt(lst):
	sys.stdout.write(' '.join(map(str, lst)) + '\n')

def outplt(lst):
	sys.stdout.write('\n'.join(map(str, lst)))

def outpltlt(lst):
	sys.stdout.write('\n'.join(map(str, (' '.join(map(str, a)) for a in lst))))
ans = []
for _ in range(inp()):
	N = inp()
	A = inlt()
	(an, openindices) = (0, [])
	for (i, a) in enumerate(A[N:]):
		if a <= N:
			openindices.append(i + N)
	for (i, a) in enumerate(A[:N]):
		if a > N:
			x = openindices.pop(-1)
			an += x - i
	ans.append(an)
outplt(ans)


for _ in range(int(input())):
	n = int(input())
	array = list(map(int, input().split()))
	(min_swap, j) = (0, 0)
	for i in range(2 * n):
		if array[i] <= n:
			min_swap += i - j
			j += 1
	print(min_swap)


for _ in range(int(input())):
	n = int(input())
	nums = list(map(int, input().split()))
	ans = 0
	itr2 = n
	for i in range(n):
		elem = nums[i]
		if elem > n:
			while nums[itr2] > n:
				itr2 += 1
			ans += itr2 - i
			itr2 += 1
	print(ans)


t = int(input())
for i in range(t):
	N = int(input())
	a = input().split(' ')
	b = []
	for k in a:
		b.append(int(k))
	z = list(range(N, 2 * N))
	c = 0
	for m in range(2 * N):
		if b[m] > N:
			c += z[0] - m
			z.pop(0)
	print(c)


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	openindices = []
	for i in range(N, 2 * N):
		if A[i] <= N:
			openindices.append(i)
	ans = 0
	for i in range(0, N):
		if A[i] > N:
			x = openindices.pop(-1)
			ans += x - i
	print(ans)


for i in range(int(input())):
	n = int(input())
	y = list(map(int, input().split()))
	z = sorted(y)
	lm = z[n - 1]
	rm = z[n]
	li = []
	ri = []
	for i in range(n):
		if y[i] > lm:
			li.append(i)
	for i in range(n, 2 * n):
		if y[i] < rm:
			ri.append(i)
	li = li[::-1]
	s = 0
	for (i, j) in zip(li, ri):
		s += abs(i - j)
	print(s)


T = int(input())
while T:
	T = T - 1
	N = int(input())
	arr = [int(x) for x in input().split()]
	(x, ans) = (0, 0)
	for i in range(2 * N):
		if arr[i] <= N:
			ans += i - x
			x += 1
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	p = [int(x) for x in input().split()]
	ans = 0
	x = 0
	for j in range(2 * n):
		if p[j] <= n:
			ans += j - x
			x += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	(left, right) = (0, 0)
	ans = 0
	for i in range(2 * n):
		if p[i] > n and i < n:
			ans += n - 1 - i - left
			left += 1
		if p[i] <= n and i >= n:
			ans += i - n - right
			right += 1
	print(ans + left * right)


t = int(input())
for t in range(t):
	n = int(input())
	arr = [int(i) for i in input().split()]
	count = 0
	i = 0
	for j in range(2 * n):
		if arr[j] <= n:
			count += j - i
			i += 1
	print(count)


t = int(input())
for i in range(t):
	n = int(input())
	A = [int(x) for x in input().split()]
	ans = 0
	count = 0
	for j in range(n):
		if A[j] > n:
			count += 1
			ans += n - j
	for j in range(n):
		if A[j + n] <= n:
			ans += j + 1
	print(ans - count)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = 0
	k = 0
	for i in range(len(l)):
		if l[i] <= n:
			ans += i - k
			k += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = 0
	queue = 0
	for i in range(2 * n):
		if l[i] <= n:
			ans = ans + i - queue
			queue = queue + 1
		if queue == n:
			break
	print(ans)


from math import sqrt, ceil, floor, gcd, log2
import sys
from sys import stdin, stdout
from collections import Counter, defaultdict, OrderedDict, deque
from itertools import combinations, groupby
from time import time
from heapq import heappop, heappush, heapify
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	mi = 0
	j = 0
	for i in range(2 * n):
		if arr[i] <= n:
			mi += i - j
			j += 1
	print(mi)


t = int(input())
while t > 0:
	n = int(input())
	l = list(map(int, input().strip().split()))
	mi = 0
	j = 0
	for i in range(2 * n):
		if l[i] <= n:
			mi += i - j
			j += 1
	print(mi)
	t -= 1


def solve(arr, n):
	sort = sorted(arr)
	(left, right) = (sort[n - 1], sort[n])
	(left_i, right_i) = ([], [])
	for i in range(0, n):
		if arr[i] > left:
			left_i.append(i)
		if arr[i + n] < right:
			right_i.append(i + n)
	ans = 0
	for i in range(len(left_i)):
		ans += abs(left_i[i] - right_i[i])
	return ans
T = int(input())
for i in range(T):
	N = int(input())
	per = list(map(int, input().split()))
	print(solve(per, N))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	sort = sorted(arr)
	(left, right) = (sort[n - 1], sort[n])
	(left_i, right_i) = ([], [])
	for i in range(0, n):
		if arr[i] > left:
			left_i.append(i)
		if arr[i + n] < right:
			right_i.append(i + n)
	ans = 0
	for i in range(len(left_i)):
		ans += abs(left_i[i] - right_i[i])
	print(ans)


a = int(input(''))
for i in range(a):
	x = int(input(''))
	t = [int(x) for x in input('').split()]
	k = list(t)
	more = less = 0
	for j in range(0, 2 * x):
		if j < x:
			if k[j] > x:
				less = less + j
		elif k[j] <= x:
			more = more + j
	print(more - less)


import math
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	mean = math.ceil(sum(arr) / (2 * n))
	ar = []
	al = []
	for i in range(n):
		if arr[i] >= mean:
			al.append([arr[i], i])
	for i in range(n, 2 * n):
		if arr[i] < mean:
			ar.append([arr[i], i])
	if len(al) != 0 and len(ar) != 0:
		tsum = 0
		for i in range(len(ar)):
			tsum += ar[i][1] - al[i][1]
		print(tsum)
	else:
		print(0)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	more = less = 0
	for j in range(0, 2 * n):
		if j < n:
			if a[j] > n:
				less += j
		elif a[j] <= n:
			more += j
	print(more - less)


t = int(input())
while t:
	t -= 1
	n = int(input())
	arr = list(map(int, input().split()))
	res = 0
	count = 0
	for x in arr:
		if x <= n:
			res += count
		else:
			count += 1
	print(res)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	for i in range(2 * n):
		(p, v) = (i < n, a[i] <= n)
		if p ^ v:
			ans += abs(n - i)
	print(ans)


def func():
	n = int(input())
	arr = [int(_) for _ in input().split()]
	res = 0
	count = 0
	for x in arr:
		if x <= n:
			res += count
		else:
			count += 1
	print(res)
for i in range(int(input())):
	func()


for i in range(int(input())):
	n = int(input())
	permutation = list(map(int, input().split()))
	num_of_ops = 0
	j = 0
	for i in range(2 * n):
		if permutation[i] > n:
			num_of_ops += n + j - i
			j += 1
	print(num_of_ops)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split(' ')))
	l1 = []
	l2 = []
	sum = 0
	for i in range(n):
		if l[i] > n:
			l1.append(i)
	for j in range(n, 2 * n):
		if l[j] <= n:
			l2.append(j)
	for i in range(len(l1)):
		sum = sum + (l2[i] - l1[i])
	print(sum)


for t in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = 0
	res = 0
	for i in l:
		if i <= n:
			res += c
		else:
			c += 1
	print(res)


def f(arr):
	n = len(arr) // 2
	h1 = 0
	h2 = 0
	count1 = 0
	count2 = 0
	for i in range(n - 1, -1, -1):
		if arr[i] > n:
			h1 += n - 1 - i - count1
			count1 += 1
	for i in range(n, len(arr)):
		if arr[i] <= n:
			h2 += i - n - count2
			count2 += 1
	return h1 + h2 + count1 ** 2
t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(el) for el in input().split(' ')]
	print(f(arr))


t = input()
for c in range(0, int(t)):
	n = input()
	p = input().split()
	arr = []
	for x in p:
		arr.append(int(x))
	count = 0
	for y in range(0, int(n)):
		if arr[y] > int(n):
			count = count + (int(n) - y)
	for z in range(int(n), 2 * int(n)):
		if arr[z] <= int(n):
			count = count + (z - int(n))
	print(count)


for i in range(int(input())):
	n = int(input())
	lst = list(map(int, input().split()))
	ans = 0
	for ii in range(n * 2):
		if lst[ii] > n:
			ans += lst[ii] - ii - 1
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	ar = list(map(int, input().split()))
	(m, k) = (0, 0)
	for i in range(2 * n):
		if ar[i] <= n:
			m += i - k
			k += 1
	print(m)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	c = 0
	ans = 0
	for i in range(2 * n):
		if l[i] <= n:
			ans += c
		else:
			c += 1
	print(ans)


for i in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	count = 0
	ans = 0
	for i in range(len(p)):
		if p[i] > n:
			count += 1
		else:
			ans += count
	print(ans)


T = int(input())
for _ in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	(res, count) = (0, 0)
	for i in a:
		if i <= n:
			res += count
		else:
			count += 1
	print(res)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ls = sorted(l)
	m = ls[n - 1]
	c = 0
	op = 0
	for i in range(n * 2):
		if l[i] <= m:
			op += i - c
			c += 1
	print(op)


t = int(input())
for i in range(t):
	n = int(input())
	p = [int(ele) for ele in input().split()][:2 * n]
	l = p.copy()
	l.sort()
	k = l[n - 1]
	t = 0
	for i in range(n):
		if p[i] > k:
			t -= i
		if p[2 * n - i - 1] <= k:
			t += 2 * n - i - 1
	print(t)


t = int(input())
for i in range(t):
	n = int(input())
	p = [int(ele) for ele in input().split()][:2 * n]
	l = p.copy()
	l.sort()
	k = l[n - 1]
	(t, r) = ([], [])
	for i in range(n):
		if p[i] > k:
			t.append(i)
		if p[2 * n - i - 1] <= k:
			r.append(2 * n - i - 1)
	s = 0
	for i in range(len(t)):
		s += r[i] - t[i]
	print(s)


for i in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	ans = 0
	for j in range(2 * n):
		if p[j] > n and j < n:
			ans = ans - j
		elif p[j] <= n and j >= n:
			ans = ans + j
	print(ans)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = []
	d = []
	for i in range(n):
		if a[i] > n:
			c.append(i)
		if a[n + i] <= n:
			d.append(n + i)
	if len(c) >= 1:
		count = 0
		m = 0
		m1 = 0
		c.sort(reverse=True)
		d.sort(reverse=True)
		for (i, j) in zip(c, d):
			m += n - 1 - i - count
			m1 += j - n - count
			count += 1
		print(m + m1 + len(c) * len(c))
	else:
		print(0)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	n = 2 * n
	cnt = 0
	res = 0
	for i in range(n):
		if arr[i] > n // 2:
			cnt += 1
		else:
			res += cnt
	print(res)


tkk = int(input())
for z in range(tkk):
	n = int(input())
	lt = list(map(int, input().split()))
	i = n
	j = n - 1
	ops = 0
	while True:
		f1 = 0
		f2 = 0
		while i > 0:
			i -= 1
			qq = lt[i]
			if qq > n:
				f1 = 1
				break
		while j < 2 * n - 1:
			j += 1
			vv = lt[j]
			if vv <= n:
				f2 = 1
				break
		if f1 == 1 or f2 == 1:
			ops += j - i
		if i == 0 and j == 2 * n - 1:
			break
	print(ops)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	h = []
	e = []
	ans = 0
	for i in range(len(l)):
		if l[i] <= n and i >= n:
			e.append(i + 1)
		if l[i] > n and i < n:
			h.append(i + 1)
	for i in range(len(h)):
		ans += abs(h[i] - e[i])
	print(ans)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	nn = 2 * n
	c = 0
	r = 0
	for i in range(nn):
		if l[i] > n:
			c = c + 1
		else:
			r = r + c
	print(r)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	n *= 2
	ls = sorted(arr)
	m = ls[n // 2 - 1]
	count = 0
	moves = 0
	for (i, val) in enumerate(arr):
		if val <= m:
			moves += i - count
			count += 1
	print(moves)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = 0
	c = 0
	for i in range(n + n):
		if a[i] <= n:
			b += i - c
			c += 1
	print(b)