In fact, the problems E1 and E2 do not have much in common. You should probably think of them as two separate problems.

You are given an integer array $a[1 \ldots n] = [a_1, a_2, \ldots, a_n]$.

Let us consider an empty deque (double-ended queue). A deque is a data structure that supports adding elements to both the beginning and the end. So, if there are elements $[3, 4, 4]$ currently in the deque, adding an element $1$ to the beginning will produce the sequence $[{1}, 3, 4, 4]$, and adding the same element to the end will produce $[3, 4, 4, {1}]$.

The elements of the array are sequentially added to the initially empty deque, starting with $a_1$ and finishing with $a_n$. Before adding each element to the deque, you may choose whether to add it to the beginning or to the end.

For example, if we consider an array $a = [3, 7, 5, 5]$, one of the possible sequences of actions looks like this:

$\quad$ 1.

add $3$ to the beginning of the deque:

deque has a sequence $[{3}]$ in it;

$\quad$ 2.

add $7$ to the end of the deque:

deque has a sequence $[3, {7}]$ in it;

$\quad$ 3.

add $5$ to the end of the deque:

deque has a sequence $[3, 7, {5}]$ in it;

$\quad$ 4.

add $5$ to the beginning of the deque:

deque has a sequence $[{5}, 3, 7, 5]$ in it;

Find the minimal possible number of inversions in the deque after the whole array is processed.

An inversion in sequence $d$ is a pair of indices $(i, j)$ such that $i < j$ and $d_i > d_j$. For example, the array $d = [5, 3, 7, 5]$ has exactly two inversions — $(1, 2)$ and $(3, 4)$, since $d_1 = 5 > 3 = d_2$ and $d_3 = 7 > 5 = d_4$.


-----Input-----

The first line contains an integer $t$ ($1 \leq t \leq 1000$) — the number of test cases.

The next $2t$ lines contain descriptions of the test cases.

The first line of each test case description contains an integer $n$ ($1 \le n \le 2 \cdot 10^5$) — array size. The second line of the description contains $n$ space-separated integers $a_i$ ($-10^9 \le a_i \le 10^9$) — elements of the array.

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


-----Output-----

Print $t$ lines, each line containing the answer to the corresponding test case. The answer to a test case should be a single integer — the minimal possible number of inversions in the deque after executing the described algorithm.


-----Examples-----

Input
6
4
3 7 5 5
3
3 2 1
3
3 1 2
4
-1 2 2 -1
4
4 5 1 3
5
1 3 1 3 2
Output
2
0
1
0
1
2


-----Note-----

One of the ways to get the sequence $[5, 3, 7, 5]$ in the deque, containing only two inversions, from the initial array $[3, 7, 5, 5]$ (the first sample test case) is described in the problem statement.

Also, in this example, you could get the answer of two inversions by simply putting each element of the original array at the end of the deque. In this case, the original sequence $[3, 7, 5, 5]$, also containing exactly two inversions, will be in the deque as-is.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Data structures

Greedy algorithms


Solutions:
from sys import stdin
input = stdin.readline
rn = lambda : int(input())
rns = lambda : map(int, input().split())
rl = lambda : list(map(int, input().split()))
rs = lambda : input().strip()
YN = lambda x: print('YES') if x else print('NO')
mod = 10 ** 9 + 7

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))
for _ in range(rn()):
	n = rn()
	a = rl()
	dp = [0, 0]
	s = SortedList([a[0]])
	for i in range(1, n):
		num = a[i]
		j = s.bisect_left(num)
		k = len(s) - s.bisect_right(num)
		take = min(dp)
		dp = [take + k, take + j]
		s.add(num)
	print(min(dp))


from bisect import bisect_left

class BIT:

	def __init__(self, n):
		self.n = n
		self.a = [0] * (n + 1)

	def update(self, x, v):
		while x <= self.n:
			self.a[x] += v
			x += x & -x

	def query(self, x):
		res = 0
		while x:
			res += self.a[x]
			x -= x & -x
		return res
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	b = sorted(arr)
	for i in range(len(arr)):
		arr[i] = bisect_left(b, arr[i]) + 1
	bit = BIT(n)
	swaps = 0
	for x in range(len(arr)):
		l = bit.query(arr[x] - 1)
		r = bit.query(arr[x])
		swaps += min(l, x - r)
		bit.update(arr[x], 1)
	print(swaps)


import sys
input = sys.stdin.readline

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	z = a.copy()
	z.sort()
	p = dict()
	s = 0
	for i in z:
		if i not in p:
			p[i] = s
			s += 1
	C = [0] * s
	F = [0] * s
	r = 0
	for i in range(n):
		v = a[i]
		c = 0
		x = p[v]
		while x >= 0:
			c += F[x]
			x = (x & x + 1) - 1
		x = p[v]
		r += min(c - C[x], i - c)
		C[x] += 1
		while x < s:
			F[x] += 1
			x = x | x + 1
	print(r)
for i in range(int(input())):
	solve()


class OsTree:

	def __init__(self, max_val=10 ** 6):
		self.N = max_val
		self.tree = [0] * (self.N + 1)
		self.size = 0

	def _cumsum(self, i):
		s = 0
		while i > 0:
			s += self.tree[i]
			i -= i & -i
		return s

	def _add(self, i, val):
		while i <= self.N:
			self.tree[i] += val
			i += i & -i

	def insert(self, val):
		self._add(val, 1)
		self.size += 1

	def get_rank(self, val):
		return self._cumsum(val)

def solve(nums, N):
	val2idx = {v: i + 1 for (i, v) in enumerate(sorted(list(set(nums))))}
	tree = OsTree(2 * 10 ** 5)
	res = 0
	for num in nums:
		idx = val2idx[num]
		smaller = tree.get_rank(idx - 1)
		bigger = tree.size - tree.get_rank(idx)
		res += min(smaller, bigger)
		tree.insert(idx)
	return res

def main():
	from sys import stdin
	T = int(stdin.readline().strip())
	for _ in range(T):
		N = int(stdin.readline().strip())
		nums = list(map(int, stdin.readline().strip().split()))
		out = solve(nums, N)
		print(out)

def test():
	from random import randint
	N = 2 * 10 ** 5
	nums_rand = [randint(-10 ** 9, 10 ** 9) for _ in range(N)]
	nums_eq = [10 ** 9] * N
	nums_inc = list(range(N))
	nums_dec = list(range(N))[::-1]
	for nums in [nums_rand, nums_eq, nums_inc, nums_dec]:
		out = solve(nums, N)
		print(out)
main()


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	z = a.copy()
	z.sort()
	p = dict()
	s = 0
	for i in z:
		if i not in p:
			p[i] = s
			s += 1
	C = [0] * s
	F = [0] * s
	r = 0
	for i in range(n):
		v = a[i]
		c = 0
		x = p[v]
		while x >= 0:
			c += F[x]
			x = (x & x + 1) - 1
		x = p[v]
		r += min(c - C[x], i - c)
		C[x] += 1
		while x < s:
			F[x] += 1
			x = x | x + 1
	print(r)


import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log2, ceil
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
from bisect import insort
from collections import Counter
from collections import deque
from heapq import heappush, heappop, heapify
from itertools import permutations, combinations
from itertools import accumulate as ac
from random import randint as ri
mod = int(1000000000.0) + 7
mod = 998244353
ip = lambda : int(stdin.readline())
inp = lambda : map(int, stdin.readline().split())
ips = lambda : stdin.readline().rstrip()
out = lambda x: stdout.write(str(x) + '\n')

class FenwickTree:

	def __init__(self, x):
		self.bit = x
		for i in range(len(x)):
			j = i | i + 1
			if j < len(x):
				x[j] += x[i]

	def update(self, idx, x):
		while idx < len(self.bit):
			self.bit[idx] += x
			idx |= idx + 1

	def query(self, end):
		x = 0
		while end:
			x += self.bit[end - 1]
			end &= end - 1
		return x
t = ip()
for _ in range(t):
	n = ip()
	arr = list(inp())
	ch = sorted(list(arr))
	dic = dd(list)
	for i in range(n):
		dic[ch[i]].append(i)
	posdic = {}
	m = {}
	for i in dic:
		dic[i].sort()
		dic[i] = deque(dic[i])
		posdic[i] = dic[i][-1]
		m[i] = dic[i][0]
	x = [0] * n
	tree = FenwickTree(x)
	inv = 0
	d = deque()
	ans = 0
	for i in arr:
		pos = dic[i].popleft()
		if len(d) == 0:
			d.append(i)
			tree.update(pos, 1)
		else:
			left = tree.query(m[i])
			max_pos = posdic[i]
			right = tree.query(n) - tree.query(max_pos + 1)
			if right < left:
				d.append(i)
				tree.update(pos, 1)
				ans += right
			else:
				d.appendleft(i)
				tree.update(pos, 1)
				ans += left
	print(ans)


import sys
import io
import math
import collections
import decimal
import itertools
import bisect
import heapq

def input():
	return sys.stdin.readline()[:-1]
INF = 10 ** 10

class BIT:

	def __init__(self, n):
		self.size = n
		self.data = [0] * (n + 1)

	def add(self, i, x):
		while i <= self.size:
			self.data[i] += x
			i += i & -i

	def get_sum(self, i):
		s = 0
		while i > 0:
			s += self.data[i]
			i -= i & -i
		return s

	def get_rsum(self, l, r):
		return self.get_sum(r) - self.get_sum(l - 1)

def solve(N, A):
	D = {a: i for (i, a) in enumerate(sorted(set(A)))}
	B = [D[a] + 1 for a in A]
	bit = BIT(N + 1)
	q = collections.deque()
	rev = 0
	for i in range(N):
		b = B[i]
		if i == 0:
			bit.add(b, 1)
		else:
			r_left = bit.get_rsum(b + 1, N + 1)
			r_right = 0
			if b > 0:
				r_right = bit.get_sum(b - 1)
			rev += min(r_left, r_right)
			bit.add(b, 1)
	return rev
T0 = int(input())
for _ in range(T0):
	N = int(input())
	A = list(map(int, input().split()))
	print(solve(N, A))


import sys
input = sys.stdin.readline

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

def II():
	return int(input().strip())

def LI():
	return [*map(int, input().strip().split())]
import copy, string, math, time, functools, fractions
from heapq import heappush, heappop, heapify
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter, OrderedDict
from itertools import permutations, chain, combinations, groupby
from operator import itemgetter
from types import GeneratorType
from typing import Iterable, TypeVar, Union

class Solution:

	def countSmaller(self, nums):
		ans = len(nums) * [0]
		arr = [[v, i] for (i, v) in enumerate(nums)]
		self.merge_sort(arr, ans)
		return ans

	def merge_sort(self, arr=[], ans=[]):
		if len(arr) <= 1:
			return
		mid = len(arr) // 2
		left_array = arr[:mid]
		right_array = arr[mid:]
		self.merge_sort(left_array, ans)
		self.merge_sort(right_array, ans)
		self.merge(left_array, right_array, arr, ans)

	def merge(self, left_array, right_array, array, ans):
		i = j = k = 0
		while i < len(left_array) and j < len(right_array):
			if left_array[i][0] <= right_array[j][0]:
				array[k] = left_array[i]
				ans[left_array[i][1]] += k - i
				i += 1
			else:
				array[k] = right_array[j]
				j += 1
			k += 1
		while i < len(left_array):
			array[k] = left_array[i]
			ans[left_array[i][1]] += k - i
			i += 1
			k += 1
		while j < len(right_array):
			array[k] = right_array[j]
			j += 1
			k += 1
for _ in range(II()):
	n = II()
	a = LI()
	q = deque([a[0]])
	k = Solution()
	s = k.countSmaller(a[::-1])[::-1]
	g = k.countSmaller([-1 * x for x in a][::-1])[::-1]
	for i in range(1, n):
		if s[i] < g[i]:
			q.appendleft(a[i])
		else:
			q.append(a[i])
	print(sum(k.countSmaller(list(q))))


import sys
from bisect import bisect
input = sys.stdin.readline

def solve():
	n = int(input())
	(*a,) = map(int, input().split())
	z = a.copy()
	z.sort()
	p = [0] * n
	F = [0] * n
	C = [0] * n
	for i in range(n):
		x = bisect(z, a[i]) - 1
		p[i] = x
		C[x] += 1
		while x < n:
			F[x] += 1
			x = x | x + 1
	r = 0
	for i in range(n - 1, -1, -1):
		c = 0
		x = p[i]
		while x >= 0:
			c += F[x]
			x = (x & x + 1) - 1
		x = p[i]
		r += min(c - C[x], i + 1 - c)
		C[x] -= 1
		while x < n:
			F[x] -= 1
			x = x | x + 1
	print(r)
for i in range(int(input())):
	solve()


import sys
readline = sys.stdin.readline
from collections import deque

class Segment_Tree:

	def __init__(self, N, f, e, lst=None):
		self.f = f
		self.e = e
		self.N = N
		if lst == None:
			self.segment_tree = [self.e] * 2 * self.N
		else:
			assert len(lst) <= self.N
			self.segment_tree = [self.e] * self.N + [x for x in lst] + [self.e] * (N - len(lst))
			for i in range(self.N - 1, 0, -1):
				self.segment_tree[i] = self.f(self.segment_tree[i << 1], self.segment_tree[i << 1 | 1])

	def __getitem__(self, i):
		if type(i) == int:
			if -self.N <= i < 0:
				return self.segment_tree[i + self.N * 2]
			elif 0 <= i < self.N:
				return self.segment_tree[i + self.N]
			else:
				raise IndexError('list index out of range')
		else:
			(a, b, c) = (i.start, i.stop, i.step)
			if a == None or a < -self.N:
				a = self.N
			elif self.N <= a:
				a = self.N * 2
			elif a < 0:
				a += self.N * 2
			else:
				a += self.N
			if b == None or self.N <= b:
				b = self.N * 2
			elif b < -self.N:
				b = self.N
			elif b < 0:
				b += self.N * 2
			else:
				b += self.N
			return self.segment_tree[slice(a, b, c)]

	def __setitem__(self, i, x):
		if -self.N <= i < 0:
			i += self.N * 2
		elif 0 <= i < self.N:
			i += self.N
		else:
			raise IndexError('list index out of range')
		self.segment_tree[i] = x
		while i > 1:
			i >>= 1
			self.segment_tree[i] = self.f(self.segment_tree[i << 1], self.segment_tree[i << 1 | 1])

	def Build(self, lst):
		for (i, x) in enumerate(lst, self.N):
			self.segment_tree[i] = x
		for i in range(self.N - 1, 0, -1):
			self.segment_tree[i] = self.f(self.segment_tree[i << 1], self.segment_tree[i << 1 | 1])

	def Fold(self, L=None, R=None):
		if L == None or L < -self.N:
			L = self.N
		elif self.N <= L:
			L = self.N * 2
		elif L < 0:
			L += self.N * 2
		else:
			L += self.N
		if R == None or self.N <= R:
			R = self.N * 2
		elif R < -self.N:
			R = self.N
		elif R < 0:
			R += self.N * 2
		else:
			R += self.N
		vL = self.e
		vR = self.e
		while L < R:
			if L & 1:
				vL = self.f(vL, self.segment_tree[L])
				L += 1
			if R & 1:
				R -= 1
				vR = self.f(self.segment_tree[R], vR)
			L >>= 1
			R >>= 1
		return self.f(vL, vR)

	def Fold_Index(self, L=None, R=None):
		if L == None or L < -self.N:
			L = self.N
		elif self.N <= L:
			L = self.N * 2
		elif L < 0:
			L += self.N * 2
		else:
			L += self.N
		if R == None or self.N <= R:
			R = self.N * 2
		elif R < -self.N:
			R = self.N
		elif R < 0:
			R += self.N * 2
		else:
			R += self.N
		if L == R:
			return None
		x = self.Fold(L - self.N, R - self.N)
		while L < R:
			if L & 1:
				if self.segment_tree[L] == x:
					i = L
					break
				L += 1
			if R & 1:
				R -= 1
				if self.segment_tree[R] == x:
					i = R
					break
			L >>= 1
			R >>= 1
		while i < self.N:
			if self.segment_tree[i] == self.segment_tree[i << 1]:
				i <<= 1
			else:
				i <<= 1
				i |= 1
		i -= self.N
		return i

	def __str__(self):
		return '[' + ', '.join(map(str, self.segment_tree[self.N:])) + ']'

def Zip(lst):
	unzip = sorted(list(set(lst)))
	zip = {x: i for (i, x) in enumerate(unzip)}
	return (zip, unzip)
T = int(readline())
for _ in range(T):
	N = int(readline())
	A = list(map(int, readline().split()))
	(zip, unzip) = Zip(A)
	l = len(zip)
	ST = Segment_Tree(l, lambda x, y: x + y, 0)
	ans = 0
	for a in A:
		a = zip[a]
		ans += min(ST.Fold(None, a), ST.Fold(a + 1, None))
		ST[a] += 1
	print(ans)


import os
import sys
from io import BytesIO, IOBase

class SortedList:

	def __init__(self, iterable=None, _load=200):
		if iterable is None:
			iterable = []
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))

def main():
	for _ in range(int(input())):
		n = int(input())
		z = list(map(int, input().split()))
		(a, b, c) = (0, 0, SortedList([z[0]]))
		for i in range(1, n):
			(x, x1) = (c.bisect_left(z[i]), len(c) - c.bisect_right(z[i]))
			if a < b:
				(a, b) = (x + a, x1 + a)
			else:
				(a, b) = (x + b, x1 + b)
			c.add(z[i])
		print(min(a, b))
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import defaultdict, deque
from math import ceil, floor, sqrt, log2, gcd, pi
from heapq import heappush, heappop
from bisect import bisect_left, bisect
from functools import reduce
import sys
abc = 'abcdefghijklmnopqrstuvwxyz'
ABC = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'

class SortedList:

	def __init__(self, iterable=None, _load=200):
		if iterable is None:
			iterable = []
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	dp = [0, 0]
	s = SortedList([arr[0]])
	for i in range(1, n):
		num = arr[i]
		j = s.bisect_left(num)
		k = len(s) - s.bisect_right(num)
		take = min(dp)
		dp = [take + j, take + k]
		s.add(num)
	print(min(dp))


import decimal
import heapq
import math
import os
import sys
from array import array
from collections import Counter, deque
from io import BytesIO, IOBase
import bisect
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

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

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

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

def output(to_be_printed, end='\n'):
	sys.stdout.write(str(to_be_printed) + end)

def ipn():
	return int(input())

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

def main():
	for _ in range(ipn()):
		n = ipn()
		a = list_get()
		bt = SortedList()
		bt.add(a[0])
		val = 0
		dic = {a[0]: 1}
		for i in range(1, n):
			x = bisect.bisect_left(bt, a[i])
			e_l = x
			e_g = i - x
			if a[i] in dic:
				e_g -= dic[a[i]]
			val += min(e_g, e_l)
			bt.add(a[i])
			if a[i] in dic:
				dic[a[i]] += 1
			else:
				dic[a[i]] = 1
		output(val)
	return
main()


import sys
input = sys.stdin.readline

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

def II():
	return int(input().strip())

def LI():
	return [*map(int, input().strip().split())]
import copy, string, math, time, functools, fractions
from heapq import heappush, heappop, heapify
from bisect import bisect_left, bisect_right
from collections import deque, defaultdict, Counter, OrderedDict
from itertools import permutations, chain, combinations, groupby
from operator import itemgetter
from types import GeneratorType
from typing import Iterable, TypeVar, Union

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))
for _ in range(II()):
	n = II()
	a = LI()
	sl = SortedList([])
	sl.add(a[0])
	ans = 0
	for i in range(1, n):
		l = sl.bisect_left(a[i])
		r = i - sl.bisect_right(a[i])
		ans += min(l, r)
		sl.add(a[i])
	print(ans)


def naiveSolve():
	return

def solve():
	return

class SegmentTree:

	def __init__(self, arr, combinerFunction, isCommutative=True):
		self.n = len(arr)

		def cmb(a, b):
			if a == None:
				return b
			if b == None:
				return a
			return combinerFunction(a, b)
		self.cmb = cmb
		self.sz = self.n if isCommutative else pow(2, (self.n - 1).bit_length())
		self.t = [None] * (2 * self.sz)
		for i in range(self.n):
			self.t[i + self.sz] = arr[i]
		for i in range(self.sz - 1, 0, -1):
			self.pull(i)

	def pull(self, p):
		self.t[p] = self.cmb(self.t[2 * p], self.t[2 * p + 1])

	def update(self, idx, val):
		idx += self.sz
		self.t[idx] = val
		idx //= 2
		while idx > 0:
			self.pull(idx)
			idx //= 2

	def query(self, l, r):
		l += self.sz
		r += self.sz + 1
		a = b = None
		while l < r:
			if l % 2 == 1:
				a = self.cmb(a, self.t[l])
				l += 1
			if r % 2 == 1:
				r -= 1
				b = self.cmb(self.t[r], b)
			l //= 2
			r //= 2
		return self.cmb(a, b)

def getMaxSegTree(arr):
	return SegmentTree(arr, lambda a, b: max(a, b), True)

def getMinSegTree(arr):
	return SegmentTree(arr, lambda a, b: min(a, b), True)

def getSumSegTree(arr):
	return SegmentTree(arr, lambda a, b: a + b, True)

def main():
	t = int(input())
	allans = []
	for _ in range(t):
		n = int(input())
		a = readIntArr()
		c = sorted(set(a))
		reverseMap = {x: i for (i, x) in enumerate(c)}
		for i in range(n):
			a[i] = reverseMap[a[i]]
		maxN = max(a) + 2
		st = getSumSegTree([0] * maxN)
		cnts = [0] * maxN
		ans = 0
		for x in a:
			if x - 1 >= 0:
				leftCnt = st.query(0, x - 1)
			else:
				leftCnt = 0
			rightCnt = st.query(x + 1, maxN - 1)
			ans += min(leftCnt, rightCnt)
			cnts[x] += 1
			st.update(x, cnts[x])
		allans.append(ans)
	multiLineArrayPrint(allans)
	return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
	dv = defaultValFactory
	da = dimensionArr
	if len(da) == 1:
		return [dv() for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(x):
	print('{}'.format(x))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ans):
	print('! {}'.format(ans))
	sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
for _abc in range(1):
	main()


from sys import stdin
input = stdin.readline

class BIT:

	def __init__(self, n):
		self.n = n
		self.tree = [0] * (n + 1)

	def sum(self, i):
		ans = 0
		i += 1
		while i > 0:
			ans += self.tree[i]
			i -= i & -i
		return ans

	def update(self, i, value):
		i += 1
		while i <= self.n:
			self.tree[i] += value
			i += i & -i
from collections import defaultdict

def f(l):
	mp = defaultdict(int)
	b = 1
	for i in sorted(list(set(l))):
		mp[i] = b
		b += 1
	bt = BIT(b + 1)
	ans = 0
	for i in l:
		i = mp[i]
		q1 = bt.sum(i - 1) - bt.sum(0)
		q2 = bt.sum(b) - bt.sum(i)
		ans += min(q1, q2)
		bt.update(i, 1)
	return ans
for _ in range(int(input())):
	a = input()
	l = list(map(int, input().strip().split()))
	print(f(l))


import sys
input = sys.stdin.readline

def make_tree(n):
	tree = [0] * (n + 1)
	return tree

def get_sum(i):
	s = 0
	while i > 0:
		s += tree[i]
		i -= i & -i
	return s

def get_sum_segment(s, t):
	ans = get_sum(t) - get_sum(s - 1)
	return ans

def add(i, x):
	while i <= n:
		tree[i] += x
		i += i & -i
t = int(input())
for _ in range(t):
	n = int(input())
	p = list(map(int, input().split()))
	tree = make_tree(n + 5)
	s = set(p)
	s = list(s)
	s.sort()
	d = dict()
	for i in range(len(s)):
		d[s[i]] = i + 1
	cnt = [0] * (n + 1)
	ans = 0
	c0 = 0
	for i in p:
		di = d[i]
		ci = cnt[di]
		s0 = get_sum(di - 1)
		ans += min(s0, c0 - ci - s0)
		add(di, 1)
		c0 += 1
		cnt[di] += 1
	print(ans)


import sys
from math import factorial, gcd
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify, nlargest, nsmallest
from itertools import groupby
from copy import deepcopy
MOD = 10 ** 9 + 7
INF = float('inf')
input = sys.stdin.readline
rl = lambda : list(map(int, input().split()))
rs = lambda : sys.stdin.readline().strip()

def update(index, val):
	while index < len(BIT):
		BIT[index] += val
		index += index & -index

def sumQuery(index):
	total = 0
	while index > 0:
		total += BIT[index]
		index -= index & -index
	return total

def rangeQuery(l, r):
	return sumQuery(r) - sumQuery(l - 1)
for _ in range(int(input())):
	n = int(input())
	A = rl()
	compressionD = {a: i + 1 for (i, a) in enumerate(sorted(set(A)))}
	A = [compressionD[a] for a in A]
	BIT = [0] * (len(compressionD) + 1)
	count = 0
	for a in A:
		x = rangeQuery(1, a - 1)
		y = rangeQuery(a + 1, len(compressionD))
		count += min(x, y)
		update(a, 1)
	print(count)


import sys, math, itertools
from collections import Counter, deque, defaultdict
from bisect import bisect_left, bisect_right
from heapq import heappop, heappush, heapify
mod = 10 ** 9 + 7
INF = float('inf')

def inp():
	return int(sys.stdin.readline())

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

def inpl_1():
	return list(map(lambda x: int(x) - 1, sys.stdin.readline().split()))

def inps():
	return sys.stdin.readline()

def inpsl(x):
	tmp = sys.stdin.readline()
	return list(tmp[:x])

def err(x):
	print(x)
	exit()

class BIT:

	def __init__(self, n):
		self.n = n
		self.data = [0] * (n + 1)
		self.el = [0] * (n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.data[i]
			i -= i & -i
		return s

	def add(self, i, x):
		self.el[i] += x
		while i <= self.n:
			self.data[i] += x
			i += i & -i

	def get(self, i, j=None):
		if j is None:
			return self.el[i]
		return self.sum(j) - self.sum(i)
for _ in range(inp()):
	n = inp()
	a = inpl()
	se = set(list(a))
	d = {}
	for (i, x) in enumerate(sorted(list(se)), 2):
		d[x] = i
	for (i, x) in enumerate(a):
		a[i] = d[x]
	bit = BIT(n + 100)
	res = 0
	for x in a:
		f = bit.get(1, x - 1)
		l = bit.get(x, n + 10)
		res += min(f, l)
		bit.add(x, 1)
	print(res)


import sys
input = sys.stdin.readline

class BIT:
	n = None
	A = None

	def __init__(self, n):
		self.n = n
		self.A = [0] * (n + 5)

	def update(self, x, val):
		while x <= self.n:
			self.A[x] += val
			x += x & -x

	def que(self, x):
		if x == 0:
			return 0
		else:
			return self.A[x] + self.que(x - (x & -x))

	def query(self, x, y):
		return self.que(y) - self.que(x - 1)
t = int(input())
for nt in range(t):
	n = int(input())
	A = [-1000000000000000.0] + list(map(int, input().split()))
	B = sorted(list(set(A)))
	for i in range(1, n + 1):
		(kir, kan) = (1, len(B) - 1)
		while kir < kan:
			mid = (kir + kan) // 2
			if A[i] > B[mid]:
				kir = mid + 1
			else:
				kan = mid
		A[i] = kir
	ft = BIT(n)
	res = 0
	for x in A[1:]:
		mn = min(ft.query(1, x - 1), ft.query(x + 1, n))
		res += mn
		ft.update(x, 1)
	print(res)


import sys
for _ in range(int(sys.stdin.readline())):
	n = int(sys.stdin.readline())
	d = [int(i) for i in sys.stdin.readline().split()][:n]
	s = sorted(d)
	(dd, last) = ({}, 1)
	for i in s:
		if not i in dd:
			dd[i] = last
			last += 1
	d = [dd[i] for i in d]
	a = [0] * (n + 1)

	def upd(x):
		while x <= n:
			a[x] += 1
			x += x & -x

	def qry(x):
		r = 0
		while x > 0:
			r += a[x]
			x -= x & -x
		return r
	r = 0
	dd = [0] * (n + 1)
	for i in range(n):
		q = qry(d[i])
		r += min(q - dd[d[i]], i - q)
		dd[d[i]] += 1
		upd(d[i])
	sys.stdout.write('%d\n' % r)


import os, sys
from io import BytesIO, IOBase
import traceback
from bisect import bisect_left, bisect_right, insort
from itertools import chain, repeat, starmap
from math import log
from operator import add, eq, ne, gt, ge, lt, le, iadd
from textwrap import dedent
from collections.abc import Sequence, MutableSequence
from functools import wraps, reduce
from _thread import get_ident

def recursive_repr(fillvalue='...'):

	def decorating_function(user_function):
		repr_running = set()

		@wraps(user_function)
		def wrapper(self):
			key = (id(self), get_ident())
			if key in repr_running:
				return fillvalue
			repr_running.add(key)
			try:
				result = user_function(self)
			finally:
				repr_running.discard(key)
			return result
		return wrapper
	return decorating_function

class SortedList(MutableSequence):
	DEFAULT_LOAD_FACTOR = 1000

	def __init__(self, iterable=None, key=None):
		assert key is None
		self._len = 0
		self._load = self.DEFAULT_LOAD_FACTOR
		self._lists = []
		self._maxes = []
		self._index = []
		self._offset = 0
		if iterable is not None:
			self._update(iterable)

	def __new__(cls, iterable=None, key=None):
		if key is None:
			return object.__new__(cls)
		elif cls is SortedList:
			return object.__new__(SortedKeyList)
		else:
			raise TypeError('inherit SortedKeyList for key argument')

	@property
	def key(self):
		return None

	def _reset(self, load):
		values = reduce(iadd, self._lists, [])
		self._clear()
		self._load = load
		self._update(values)

	def clear(self):
		self._len = 0
		del self._lists[:]
		del self._maxes[:]
		del self._index[:]
		self._offset = 0
	_clear = clear

	def add(self, value):
		_lists = self._lists
		_maxes = self._maxes
		if _maxes:
			pos = bisect_right(_maxes, value)
			if pos == len(_maxes):
				pos -= 1
				_lists[pos].append(value)
				_maxes[pos] = value
			else:
				insort(_lists[pos], value)
			self._expand(pos)
		else:
			_lists.append([value])
			_maxes.append(value)
		self._len += 1

	def _expand(self, pos):
		_load = self._load
		_lists = self._lists
		_index = self._index
		if len(_lists[pos]) > _load << 1:
			_maxes = self._maxes
			_lists_pos = _lists[pos]
			half = _lists_pos[_load:]
			del _lists_pos[_load:]
			_maxes[pos] = _lists_pos[-1]
			_lists.insert(pos + 1, half)
			_maxes.insert(pos + 1, half[-1])
			del _index[:]
		elif _index:
			child = self._offset + pos
			while child:
				_index[child] += 1
				child = child - 1 >> 1
			_index[0] += 1

	def update(self, iterable):
		_lists = self._lists
		_maxes = self._maxes
		values = sorted(iterable)
		if _maxes:
			if len(values) * 4 >= self._len:
				_lists.append(values)
				values = reduce(iadd, _lists, [])
				values.sort()
				self._clear()
			else:
				_add = self.add
				for val in values:
					_add(val)
				return
		_load = self._load
		_lists.extend((values[pos:pos + _load] for pos in range(0, len(values), _load)))
		_maxes.extend((sublist[-1] for sublist in _lists))
		self._len = len(values)
		del self._index[:]
	_update = update

	def __contains__(self, value):
		_maxes = self._maxes
		if not _maxes:
			return False
		pos = bisect_left(_maxes, value)
		if pos == len(_maxes):
			return False
		_lists = self._lists
		idx = bisect_left(_lists[pos], value)
		return _lists[pos][idx] == value

	def discard(self, value):
		_maxes = self._maxes
		if not _maxes:
			return
		pos = bisect_left(_maxes, value)
		if pos == len(_maxes):
			return
		_lists = self._lists
		idx = bisect_left(_lists[pos], value)
		if _lists[pos][idx] == value:
			self._delete(pos, idx)

	def remove(self, value):
		_maxes = self._maxes
		if not _maxes:
			raise ValueError('{0!r} not in list'.format(value))
		pos = bisect_left(_maxes, value)
		if pos == len(_maxes):
			raise ValueError('{0!r} not in list'.format(value))
		_lists = self._lists
		idx = bisect_left(_lists[pos], value)
		if _lists[pos][idx] == value:
			self._delete(pos, idx)
		else:
			raise ValueError('{0!r} not in list'.format(value))

	def _delete(self, pos, idx):
		_lists = self._lists
		_maxes = self._maxes
		_index = self._index
		_lists_pos = _lists[pos]
		del _lists_pos[idx]
		self._len -= 1
		len_lists_pos = len(_lists_pos)
		if len_lists_pos > self._load >> 1:
			_maxes[pos] = _lists_pos[-1]
			if _index:
				child = self._offset + pos
				while child > 0:
					_index[child] -= 1
					child = child - 1 >> 1
				_index[0] -= 1
		elif len(_lists) > 1:
			if not pos:
				pos += 1
			prev = pos - 1
			_lists[prev].extend(_lists[pos])
			_maxes[prev] = _lists[prev][-1]
			del _lists[pos]
			del _maxes[pos]
			del _index[:]
			self._expand(prev)
		elif len_lists_pos:
			_maxes[pos] = _lists_pos[-1]
		else:
			del _lists[pos]
			del _maxes[pos]
			del _index[:]

	def _loc(self, pos, idx):
		if not pos:
			return idx
		_index = self._index
		if not _index:
			self._build_index()
		total = 0
		pos += self._offset
		while pos:
			if not pos & 1:
				total += _index[pos - 1]
			pos = pos - 1 >> 1
		return total + idx

	def _pos(self, idx):
		if idx < 0:
			last_len = len(self._lists[-1])
			if -idx <= last_len:
				return (len(self._lists) - 1, last_len + idx)
			idx += self._len
			if idx < 0:
				raise IndexError('list index out of range')
		elif idx >= self._len:
			raise IndexError('list index out of range')
		if idx < len(self._lists[0]):
			return (0, idx)
		_index = self._index
		if not _index:
			self._build_index()
		pos = 0
		child = 1
		len_index = len(_index)
		while child < len_index:
			index_child = _index[child]
			if idx < index_child:
				pos = child
			else:
				idx -= index_child
				pos = child + 1
			child = (pos << 1) + 1
		return (pos - self._offset, idx)

	def _build_index(self):
		row0 = list(map(len, self._lists))
		if len(row0) == 1:
			self._index[:] = row0
			self._offset = 0
			return
		head = iter(row0)
		tail = iter(head)
		row1 = list(starmap(add, zip(head, tail)))
		if len(row0) & 1:
			row1.append(row0[-1])
		if len(row1) == 1:
			self._index[:] = row1 + row0
			self._offset = 1
			return
		size = 2 ** (int(log(len(row1) - 1, 2)) + 1)
		row1.extend(repeat(0, size - len(row1)))
		tree = [row0, row1]
		while len(tree[-1]) > 1:
			head = iter(tree[-1])
			tail = iter(head)
			row = list(starmap(add, zip(head, tail)))
			tree.append(row)
		reduce(iadd, reversed(tree), self._index)
		self._offset = size * 2 - 1

	def __delitem__(self, index):
		if isinstance(index, slice):
			(start, stop, step) = index.indices(self._len)
			if step == 1 and start < stop:
				if start == 0 and stop == self._len:
					return self._clear()
				elif self._len <= 8 * (stop - start):
					values = self._getitem(slice(None, start))
					if stop < self._len:
						values += self._getitem(slice(stop, None))
					self._clear()
					return self._update(values)
			indices = range(start, stop, step)
			if step > 0:
				indices = reversed(indices)
			(_pos, _delete) = (self._pos, self._delete)
			for index in indices:
				(pos, idx) = _pos(index)
				_delete(pos, idx)
		else:
			(pos, idx) = self._pos(index)
			self._delete(pos, idx)

	def __getitem__(self, index):
		_lists = self._lists
		if isinstance(index, slice):
			(start, stop, step) = index.indices(self._len)
			if step == 1 and start < stop:
				if start == 0 and stop == self._len:
					return reduce(iadd, self._lists, [])
				(start_pos, start_idx) = self._pos(start)
				start_list = _lists[start_pos]
				stop_idx = start_idx + stop - start
				if len(start_list) >= stop_idx:
					return start_list[start_idx:stop_idx]
				if stop == self._len:
					stop_pos = len(_lists) - 1
					stop_idx = len(_lists[stop_pos])
				else:
					(stop_pos, stop_idx) = self._pos(stop)
				prefix = _lists[start_pos][start_idx:]
				middle = _lists[start_pos + 1:stop_pos]
				result = reduce(iadd, middle, prefix)
				result += _lists[stop_pos][:stop_idx]
				return result
			if step == -1 and start > stop:
				result = self._getitem(slice(stop + 1, start + 1))
				result.reverse()
				return result
			indices = range(start, stop, step)
			return list((self._getitem(index) for index in indices))
		else:
			if self._len:
				if index == 0:
					return _lists[0][0]
				elif index == -1:
					return _lists[-1][-1]
			else:
				raise IndexError('list index out of range')
			if 0 <= index < len(_lists[0]):
				return _lists[0][index]
			len_last = len(_lists[-1])
			if -len_last < index < 0:
				return _lists[-1][len_last + index]
			(pos, idx) = self._pos(index)
			return _lists[pos][idx]
	_getitem = __getitem__

	def __setitem__(self, index, value):
		message = 'use ``del sl[index]`` and ``sl.add(value)`` instead'
		raise NotImplementedError(message)

	def __iter__(self):
		return chain.from_iterable(self._lists)

	def __reversed__(self):
		return chain.from_iterable(map(reversed, reversed(self._lists)))

	def reverse(self):
		raise NotImplementedError('use ``reversed(sl)`` instead')

	def islice(self, start=None, stop=None, reverse=False):
		_len = self._len
		if not _len:
			return iter(())
		(start, stop, _) = slice(start, stop).indices(self._len)
		if start >= stop:
			return iter(())
		_pos = self._pos
		(min_pos, min_idx) = _pos(start)
		if stop == _len:
			max_pos = len(self._lists) - 1
			max_idx = len(self._lists[-1])
		else:
			(max_pos, max_idx) = _pos(stop)
		return self._islice(min_pos, min_idx, max_pos, max_idx, reverse)

	def _islice(self, min_pos, min_idx, max_pos, max_idx, reverse):
		_lists = self._lists
		if min_pos > max_pos:
			return iter(())
		if min_pos == max_pos:
			if reverse:
				indices = reversed(range(min_idx, max_idx))
				return map(_lists[min_pos].__getitem__, indices)
			indices = range(min_idx, max_idx)
			return map(_lists[min_pos].__getitem__, indices)
		next_pos = min_pos + 1
		if next_pos == max_pos:
			if reverse:
				min_indices = range(min_idx, len(_lists[min_pos]))
				max_indices = range(max_idx)
				return chain(map(_lists[max_pos].__getitem__, reversed(max_indices)), map(_lists[min_pos].__getitem__, reversed(min_indices)))
			min_indices = range(min_idx, len(_lists[min_pos]))
			max_indices = range(max_idx)
			return chain(map(_lists[min_pos].__getitem__, min_indices), map(_lists[max_pos].__getitem__, max_indices))
		if reverse:
			min_indices = range(min_idx, len(_lists[min_pos]))
			sublist_indices = range(next_pos, max_pos)
			sublists = map(_lists.__getitem__, reversed(sublist_indices))
			max_indices = range(max_idx)
			return chain(map(_lists[max_pos].__getitem__, reversed(max_indices)), chain.from_iterable(map(reversed, sublists)), map(_lists[min_pos].__getitem__, reversed(min_indices)))
		min_indices = range(min_idx, len(_lists[min_pos]))
		sublist_indices = range(next_pos, max_pos)
		sublists = map(_lists.__getitem__, sublist_indices)
		max_indices = range(max_idx)
		return chain(map(_lists[min_pos].__getitem__, min_indices), chain.from_iterable(sublists), map(_lists[max_pos].__getitem__, max_indices))

	def irange(self, minimum=None, maximum=None, inclusive=(True, True), reverse=False):
		_maxes = self._maxes
		if not _maxes:
			return iter(())
		_lists = self._lists
		if minimum is None:
			min_pos = 0
			min_idx = 0
		elif inclusive[0]:
			min_pos = bisect_left(_maxes, minimum)
			if min_pos == len(_maxes):
				return iter(())
			min_idx = bisect_left(_lists[min_pos], minimum)
		else:
			min_pos = bisect_right(_maxes, minimum)
			if min_pos == len(_maxes):
				return iter(())
			min_idx = bisect_right(_lists[min_pos], minimum)
		if maximum is None:
			max_pos = len(_maxes) - 1
			max_idx = len(_lists[max_pos])
		elif inclusive[1]:
			max_pos = bisect_right(_maxes, maximum)
			if max_pos == len(_maxes):
				max_pos -= 1
				max_idx = len(_lists[max_pos])
			else:
				max_idx = bisect_right(_lists[max_pos], maximum)
		else:
			max_pos = bisect_left(_maxes, maximum)
			if max_pos == len(_maxes):
				max_pos -= 1
				max_idx = len(_lists[max_pos])
			else:
				max_idx = bisect_left(_lists[max_pos], maximum)
		return self._islice(min_pos, min_idx, max_pos, max_idx, reverse)

	def __len__(self):
		return self._len

	def bisect_left(self, value):
		_maxes = self._maxes
		if not _maxes:
			return 0
		pos = bisect_left(_maxes, value)
		if pos == len(_maxes):
			return self._len
		idx = bisect_left(self._lists[pos], value)
		return self._loc(pos, idx)

	def bisect_right(self, value):
		_maxes = self._maxes
		if not _maxes:
			return 0
		pos = bisect_right(_maxes, value)
		if pos == len(_maxes):
			return self._len
		idx = bisect_right(self._lists[pos], value)
		return self._loc(pos, idx)
	bisect = bisect_right
	_bisect_right = bisect_right

	def count(self, value):
		_maxes = self._maxes
		if not _maxes:
			return 0
		pos_left = bisect_left(_maxes, value)
		if pos_left == len(_maxes):
			return 0
		_lists = self._lists
		idx_left = bisect_left(_lists[pos_left], value)
		pos_right = bisect_right(_maxes, value)
		if pos_right == len(_maxes):
			return self._len - self._loc(pos_left, idx_left)
		idx_right = bisect_right(_lists[pos_right], value)
		if pos_left == pos_right:
			return idx_right - idx_left
		right = self._loc(pos_right, idx_right)
		left = self._loc(pos_left, idx_left)
		return right - left

	def copy(self):
		return self.__class__(self)
	__copy__ = copy

	def append(self, value):
		raise NotImplementedError('use ``sl.add(value)`` instead')

	def extend(self, values):
		raise NotImplementedError('use ``sl.update(values)`` instead')

	def insert(self, index, value):
		raise NotImplementedError('use ``sl.add(value)`` instead')

	def pop(self, index=-1):
		if not self._len:
			raise IndexError('pop index out of range')
		_lists = self._lists
		if index == 0:
			val = _lists[0][0]
			self._delete(0, 0)
			return val
		if index == -1:
			pos = len(_lists) - 1
			loc = len(_lists[pos]) - 1
			val = _lists[pos][loc]
			self._delete(pos, loc)
			return val
		if 0 <= index < len(_lists[0]):
			val = _lists[0][index]
			self._delete(0, index)
			return val
		len_last = len(_lists[-1])
		if -len_last < index < 0:
			pos = len(_lists) - 1
			loc = len_last + index
			val = _lists[pos][loc]
			self._delete(pos, loc)
			return val
		(pos, idx) = self._pos(index)
		val = _lists[pos][idx]
		self._delete(pos, idx)
		return val

	def index(self, value, start=None, stop=None):
		_len = self._len
		if not _len:
			raise ValueError('{0!r} is not in list'.format(value))
		if start is None:
			start = 0
		if start < 0:
			start += _len
		if start < 0:
			start = 0
		if stop is None:
			stop = _len
		if stop < 0:
			stop += _len
		if stop > _len:
			stop = _len
		if stop <= start:
			raise ValueError('{0!r} is not in list'.format(value))
		_maxes = self._maxes
		pos_left = bisect_left(_maxes, value)
		if pos_left == len(_maxes):
			raise ValueError('{0!r} is not in list'.format(value))
		_lists = self._lists
		idx_left = bisect_left(_lists[pos_left], value)
		if _lists[pos_left][idx_left] != value:
			raise ValueError('{0!r} is not in list'.format(value))
		stop -= 1
		left = self._loc(pos_left, idx_left)
		if start <= left:
			if left <= stop:
				return left
		else:
			right = self._bisect_right(value) - 1
			if start <= right:
				return start
		raise ValueError('{0!r} is not in list'.format(value))

	def __add__(self, other):
		values = reduce(iadd, self._lists, [])
		values.extend(other)
		return self.__class__(values)
	__radd__ = __add__

	def __iadd__(self, other):
		self._update(other)
		return self

	def __mul__(self, num):
		values = reduce(iadd, self._lists, []) * num
		return self.__class__(values)
	__rmul__ = __mul__

	def __imul__(self, num):
		values = reduce(iadd, self._lists, []) * num
		self._clear()
		self._update(values)
		return self

	def __make_cmp(seq_op, symbol, doc):

		def comparer(self, other):
			if not isinstance(other, Sequence):
				return NotImplemented
			self_len = self._len
			len_other = len(other)
			if self_len != len_other:
				if seq_op is eq:
					return False
				if seq_op is ne:
					return True
			for (alpha, beta) in zip(self, other):
				if alpha != beta:
					return seq_op(alpha, beta)
			return seq_op(self_len, len_other)
		seq_op_name = seq_op.__name__
		comparer.__name__ = '__{0}__'.format(seq_op_name)
		doc_str = 'Return true if and only if sorted list is {0} `other`.\n        ``sl.__{1}__(other)`` <==> ``sl {2} other``\n        Comparisons use lexicographical order as with sequences.\n        Runtime complexity: `O(n)`\n        :param other: `other` sequence\n        :return: true if sorted list is {0} `other`\n        '
		comparer.__doc__ = dedent(doc_str.format(doc, seq_op_name, symbol))
		return comparer
	__eq__ = __make_cmp(eq, '==', 'equal to')
	__ne__ = __make_cmp(ne, '!=', 'not equal to')
	__lt__ = __make_cmp(lt, '<', 'less than')
	__gt__ = __make_cmp(gt, '>', 'greater than')
	__le__ = __make_cmp(le, '<=', 'less than or equal to')
	__ge__ = __make_cmp(ge, '>=', 'greater than or equal to')
	__make_cmp = staticmethod(__make_cmp)

	def __reduce__(self):
		values = reduce(iadd, self._lists, [])
		return (type(self), (values,))

	@recursive_repr()
	def __repr__(self):
		return '{0}({1!r})'.format(type(self).__name__, list(self))

	def _check(self):
		try:
			assert self._load >= 4
			assert len(self._maxes) == len(self._lists)
			assert self._len == sum((len(sublist) for sublist in self._lists))
			for sublist in self._lists:
				for pos in range(1, len(sublist)):
					assert sublist[pos - 1] <= sublist[pos]
			for pos in range(1, len(self._lists)):
				assert self._lists[pos - 1][-1] <= self._lists[pos][0]
			for pos in range(len(self._maxes)):
				assert self._maxes[pos] == self._lists[pos][-1]
			double = self._load << 1
			assert all((len(sublist) <= double for sublist in self._lists))
			half = self._load >> 1
			for pos in range(0, len(self._lists) - 1):
				assert len(self._lists[pos]) >= half
			if self._index:
				assert self._len == self._index[0]
				assert len(self._index) == self._offset + len(self._lists)
				for pos in range(len(self._lists)):
					leaf = self._index[self._offset + pos]
					assert leaf == len(self._lists[pos])
				for pos in range(self._offset):
					child = (pos << 1) + 1
					if child >= len(self._index):
						assert self._index[pos] == 0
					elif child + 1 == len(self._index):
						assert self._index[pos] == self._index[child]
					else:
						child_sum = self._index[child] + self._index[child + 1]
						assert child_sum == self._index[pos]
		except:
			traceback.print_exc(file=sys.stdout)
			print('len', self._len)
			print('load', self._load)
			print('offset', self._offset)
			print('len_index', len(self._index))
			print('index', self._index)
			print('len_maxes', len(self._maxes))
			print('maxes', self._maxes)
			print('len_lists', len(self._lists))
			print('lists', self._lists)
			raise

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, 8192))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, 8192))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
inp = lambda dtype: [dtype(x) for x in input().split()]
inp_2d = lambda dtype, n: [dtype(input()) for _ in range(n)]
inp_2ds = lambda dtype, n: [inp(dtype) for _ in range(n)]
inp_enu = lambda dtype: [(i, x) for (i, x) in enumerate(inp(dtype))]
inp_enus = lambda dtype, n: [[i] + inp(dtype) for i in range(n)]
ceil1 = lambda a, b: (a + b - 1) // b
for _ in range(int(input())):
	(n, a, ans) = (int(input()), inp(int), 0)
	sor = SortedList([a[0]])
	for i in range(1, n):
		(l, r) = (sor.bisect_left(a[i]) - 1, sor.bisect_right(a[i]))
		ans += min(l + 1, len(sor) - r)
		sor.add(a[i])
	print(ans)


import sys
input = sys.stdin.readline

def update(inp, add, ar):
	global n
	while inp < n + 1:
		ar[inp] += add
		inp += inp & -inp

def summation(inp, ar):
	ans = 0
	while inp:
		ans += ar[inp]
		inp -= inp & -inp
	return ans
for _ in range(int(input())):
	n = int(input())
	br = list(map(int, input().split()))
	li = list(set(br))
	li.sort()
	dic = {}
	for i in range(len(li)):
		dic[li[i]] = i
	sort_ind = [dic[i] + 1 for i in br]
	ar = [0] * (n + 1)
	ans = 0
	update(sort_ind[0], 1, ar)
	for i in range(1, n):
		sind = sort_ind[i]
		tot = i
		sm = summation(sind - 1, ar)
		la = tot - summation(sind, ar)
		ans += min(sm, la)
		update(sind, 1, ar)
	print(ans)


from __future__ import print_function
u = 'lists'
t = 'len_lists'
s = 'maxes'
r = 'len_maxes'
q = 'index'
p = 'len_index'
o = 'offset'
n = 'load'
m = 'len'
l = 'use ``sl.add(value)`` instead'
k = all
j = sum
i = sorted
h = property
c = 'list index out of range'
b = isinstance
a = ImportError
S = type
R = IndexError
Q = NotImplementedError
P = slice
O = '{0!r} not in list'
N = list
L = '{0!r} is not in list'
K = False
J = reversed
I = True
H = iter
E = ValueError
D = print
C = range
B = None
A = len
import sys, traceback as T
from bisect import bisect_left, bisect_right, insort as d
from itertools import chain as M, repeat as e, starmap as U
from math import log
from operator import add, eq, ne, gt, ge, lt, le, iadd as F
from textwrap import dedent as f
try:
	from collections.abc import Sequence, MutableSequence as V
except a:
	from collections import Sequence, MutableSequence as V
from functools import wraps
from sys import hexversion as g
if g < 50331648:
	from itertools import imap as map, izip as zip
	try:
		from thread import get_ident
	except a:
		from dummy_thread import get_ident
else:
	from functools import reduce as G
	try:
		from _thread import get_ident
	except a:
		from _dummy_thread import get_ident

def W(fillvalue='...'):

	def A(user_function):
		C = user_function
		A = set()

		@wraps(C)
		def B(self):
			B = (id(self), get_ident())
			if B in A:
				return fillvalue
			A.add(B)
			try:
				D = C(self)
			finally:
				A.discard(B)
			return D
		return B
	return A

class X(V):
	DEFAULT_LOAD_FACTOR = 1000

	def __init__(A, iterable=B, key=B):
		C = iterable
		assert key is B
		A._len = 0
		A._load = A.DEFAULT_LOAD_FACTOR
		A._lists = []
		A._maxes = []
		A._index = []
		A._offset = 0
		if C is not B:
			A._update(C)

	def __new__(A, iterable=B, key=B):
		if key is B:
			return object.__new__(A)
		elif A is X:
			return object.__new__(Z)
		else:
			raise TypeError('inherit SortedKeyList for key argument')

	@h
	def key(self):
		return B

	def _reset(A, load):
		B = G(F, A._lists, [])
		A._clear()
		A._load = load
		A._update(B)

	def clear(A):
		A._len = 0
		del A._lists[:]
		del A._maxes[:]
		del A._index[:]
		A._offset = 0
	_clear = clear

	def add(E, value):
		B = value
		F = E._lists
		D = E._maxes
		if D:
			C = bisect_right(D, B)
			if C == A(D):
				C -= 1
				F[C].append(B)
				D[C] = B
			else:
				d(F[C], B)
			E._expand(C)
		else:
			F.append([B])
			D.append(B)
		E._len += 1

	def _expand(C, pos):
		B = pos
		F = C._load
		G = C._lists
		D = C._index
		if A(G[B]) > F << 1:
			I = C._maxes
			H = G[B]
			J = H[F:]
			del H[F:]
			I[B] = H[-1]
			G.insert(B + 1, J)
			I.insert(B + 1, J[-1])
			del D[:]
		elif D:
			E = C._offset + B
			while E:
				D[E] += 1
				E = E - 1 >> 1
			D[0] += 1

	def update(B, iterable):
		E = B._lists
		H = B._maxes
		D = i(iterable)
		if H:
			if A(D) * 4 >= B._len:
				E.append(D)
				D = G(F, E, [])
				D.sort()
				B._clear()
			else:
				J = B.add
				for K in D:
					J(K)
				return
		I = B._load
		E.extend((D[B:B + I] for B in C(0, A(D), I)))
		H.extend((A[-1] for A in E))
		B._len = A(D)
		del B._index[:]
	_update = update

	def __contains__(E, value):
		B = value
		C = E._maxes
		if not C:
			return K
		D = bisect_left(C, B)
		if D == A(C):
			return K
		F = E._lists
		G = bisect_left(F[D], B)
		return F[D][G] == B

	def discard(C, value):
		D = value
		E = C._maxes
		if not E:
			return
		B = bisect_left(E, D)
		if B == A(E):
			return
		F = C._lists
		G = bisect_left(F[B], D)
		if F[B][G] == D:
			C._delete(B, G)

	def remove(D, value):
		B = value
		F = D._maxes
		if not F:
			raise E(O.format(B))
		C = bisect_left(F, B)
		if C == A(F):
			raise E(O.format(B))
		G = D._lists
		H = bisect_left(G[C], B)
		if G[C][H] == B:
			D._delete(C, H)
		else:
			raise E(O.format(B))

	def _delete(C, pos, idx):
		B = pos
		D = C._lists
		E = C._maxes
		F = C._index
		G = D[B]
		del G[idx]
		C._len -= 1
		J = A(G)
		if J > C._load >> 1:
			E[B] = G[-1]
			if F:
				H = C._offset + B
				while H > 0:
					F[H] -= 1
					H = H - 1 >> 1
				F[0] -= 1
		elif A(D) > 1:
			if not B:
				B += 1
			I = B - 1
			D[I].extend(D[B])
			E[I] = D[I][-1]
			del D[B]
			del E[B]
			del F[:]
			C._expand(I)
		elif J:
			E[B] = G[-1]
		else:
			del D[B]
			del E[B]
			del F[:]

	def _loc(B, pos, idx):
		A = pos
		if not A:
			return idx
		C = B._index
		if not C:
			B._build_index()
		D = 0
		A += B._offset
		while A:
			if not A & 1:
				D += C[A - 1]
			A = A - 1 >> 1
		return D + idx

	def _pos(C, idx):
		B = idx
		if B < 0:
			G = A(C._lists[-1])
			if -B <= G:
				return (A(C._lists) - 1, G + B)
			B += C._len
			if B < 0:
				raise R(c)
		elif B >= C._len:
			raise R(c)
		if B < A(C._lists[0]):
			return (0, B)
		F = C._index
		if not F:
			C._build_index()
		E = 0
		D = 1
		I = A(F)
		while D < I:
			H = F[D]
			if B < H:
				E = D
			else:
				B -= H
				E = D + 1
			D = (E << 1) + 1
		return (E - C._offset, B)

	def _build_index(B):
		C = N(map(A, B._lists))
		if A(C) == 1:
			B._index[:] = C
			B._offset = 0
			return
		E = H(C)
		K = H(E)
		D = N(U(add, zip(E, K)))
		if A(C) & 1:
			D.append(C[-1])
		if A(D) == 1:
			B._index[:] = D + C
			B._offset = 1
			return
		L = 2 ** (int(log(A(D) - 1, 2)) + 1)
		D.extend(e(0, L - A(D)))
		I = [C, D]
		while A(I[-1]) > 1:
			E = H(I[-1])
			K = H(E)
			M = N(U(add, zip(E, K)))
			I.append(M)
		G(F, J(I), B._index)
		B._offset = L * 2 - 1

	def __delitem__(A, index):
		E = index
		if b(E, P):
			(F, D, G) = E.indices(A._len)
			if G == 1 and F < D:
				if F == 0 and D == A._len:
					return A._clear()
				elif A._len <= 8 * (D - F):
					L = A._getitem(P(B, F))
					if D < A._len:
						L += A._getitem(P(D, B))
					A._clear()
					return A._update(L)
			H = C(F, D, G)
			if G > 0:
				H = J(H)
			(M, N) = (A._pos, A._delete)
			for E in H:
				(I, K) = M(E)
				N(I, K)
		else:
			(I, K) = A._pos(E)
			A._delete(I, K)

	def __getitem__(D, index):
		E = index
		B = D._lists
		if b(E, P):
			(I, H, M) = E.indices(D._len)
			if M == 1 and I < H:
				if I == 0 and H == D._len:
					return G(F, D._lists, [])
				(O, Q) = D._pos(I)
				S = B[O]
				J = Q + H - I
				if A(S) >= J:
					return S[Q:J]
				if H == D._len:
					L = A(B) - 1
					J = A(B[L])
				else:
					(L, J) = D._pos(H)
				U = B[O][Q:]
				V = B[O + 1:L]
				K = G(F, V, U)
				K += B[L][:J]
				return K
			if M == -1 and I > H:
				K = D._getitem(P(H + 1, I + 1))
				K.reverse()
				return K
			W = C(I, H, M)
			return N((D._getitem(A) for A in W))
		else:
			if D._len:
				if E == 0:
					return B[0][0]
				elif E == -1:
					return B[-1][-1]
			else:
				raise R(c)
			if 0 <= E < A(B[0]):
				return B[0][E]
			T = A(B[-1])
			if -T < E < 0:
				return B[-1][T + E]
			(X, Y) = D._pos(E)
			return B[X][Y]
	_getitem = __getitem__

	def __setitem__(B, index, value):
		A = 'use ``del sl[index]`` and ``sl.add(value)`` instead'
		raise Q(A)

	def __iter__(A):
		return M.from_iterable(A._lists)

	def __reversed__(A):
		return M.from_iterable(map(J, J(A._lists)))

	def reverse(A):
		raise Q('use ``reversed(sl)`` instead')

	def islice(B, start=B, stop=B, reverse=K):
		D = start
		C = stop
		E = B._len
		if not E:
			return H(())
		(D, C, L) = P(D, C).indices(B._len)
		if D >= C:
			return H(())
		F = B._pos
		(J, K) = F(D)
		if C == E:
			G = A(B._lists) - 1
			I = A(B._lists[-1])
		else:
			(G, I) = F(C)
		return B._islice(J, K, G, I, reverse)

	def _islice(R, min_pos, min_idx, max_pos, max_idx, reverse):
		L = reverse
		K = max_idx
		I = min_idx
		E = max_pos
		D = min_pos
		B = R._lists
		if D > E:
			return H(())
		if D == E:
			if L:
				N = J(C(I, K))
				return map(B[D].__getitem__, N)
			N = C(I, K)
			return map(B[D].__getitem__, N)
		O = D + 1
		if O == E:
			if L:
				F = C(I, A(B[D]))
				G = C(K)
				return M(map(B[E].__getitem__, J(G)), map(B[D].__getitem__, J(F)))
			F = C(I, A(B[D]))
			G = C(K)
			return M(map(B[D].__getitem__, F), map(B[E].__getitem__, G))
		if L:
			F = C(I, A(B[D]))
			P = C(O, E)
			Q = map(B.__getitem__, J(P))
			G = C(K)
			return M(map(B[E].__getitem__, J(G)), M.from_iterable(map(J, Q)), map(B[D].__getitem__, J(F)))
		F = C(I, A(B[D]))
		P = C(O, E)
		Q = map(B.__getitem__, P)
		G = C(K)
		return M(map(B[D].__getitem__, F), M.from_iterable(Q), map(B[E].__getitem__, G))

	def irange(K, minimum=B, maximum=B, inclusive=(I, I), reverse=K):
		M = inclusive
		I = maximum
		G = minimum
		D = K._maxes
		if not D:
			return H(())
		E = K._lists
		if G is B:
			F = 0
			L = 0
		elif M[0]:
			F = bisect_left(D, G)
			if F == A(D):
				return H(())
			L = bisect_left(E[F], G)
		else:
			F = bisect_right(D, G)
			if F == A(D):
				return H(())
			L = bisect_right(E[F], G)
		if I is B:
			C = A(D) - 1
			J = A(E[C])
		elif M[1]:
			C = bisect_right(D, I)
			if C == A(D):
				C -= 1
				J = A(E[C])
			else:
				J = bisect_right(E[C], I)
		else:
			C = bisect_left(D, I)
			if C == A(D):
				C -= 1
				J = A(E[C])
			else:
				J = bisect_left(E[C], I)
		return K._islice(F, L, C, J, reverse)

	def __len__(A):
		return A._len

	def bisect_left(B, value):
		E = value
		C = B._maxes
		if not C:
			return 0
		D = bisect_left(C, E)
		if D == A(C):
			return B._len
		F = bisect_left(B._lists[D], E)
		return B._loc(D, F)

	def bisect_right(B, value):
		E = value
		C = B._maxes
		if not C:
			return 0
		D = bisect_right(C, E)
		if D == A(C):
			return B._len
		F = bisect_right(B._lists[D], E)
		return B._loc(D, F)
	bisect = bisect_right
	_bisect_right = bisect_right

	def count(B, value):
		E = value
		C = B._maxes
		if not C:
			return 0
		D = bisect_left(C, E)
		if D == A(C):
			return 0
		H = B._lists
		G = bisect_left(H[D], E)
		F = bisect_right(C, E)
		if F == A(C):
			return B._len - B._loc(D, G)
		I = bisect_right(H[F], E)
		if D == F:
			return I - G
		J = B._loc(F, I)
		K = B._loc(D, G)
		return J - K

	def copy(A):
		return A.__class__(A)
	__copy__ = copy

	def append(A, value):
		raise Q(l)

	def extend(A, values):
		raise Q('use ``sl.update(values)`` instead')

	def insert(A, index, value):
		raise Q(l)

	def pop(E, index=-1):
		F = index
		if not E._len:
			raise R('pop index out of range')
		B = E._lists
		if F == 0:
			C = B[0][0]
			E._delete(0, 0)
			return C
		if F == -1:
			D = A(B) - 1
			G = A(B[D]) - 1
			C = B[D][G]
			E._delete(D, G)
			return C
		if 0 <= F < A(B[0]):
			C = B[0][F]
			E._delete(0, F)
			return C
		H = A(B[-1])
		if -H < F < 0:
			D = A(B) - 1
			G = H + F
			C = B[D][G]
			E._delete(D, G)
			return C
		(D, I) = E._pos(F)
		C = B[D][I]
		E._delete(D, I)
		return C

	def index(H, value, start=B, stop=B):
		F = stop
		D = value
		C = start
		G = H._len
		if not G:
			raise E(L.format(D))
		if C is B:
			C = 0
		if C < 0:
			C += G
		if C < 0:
			C = 0
		if F is B:
			F = G
		if F < 0:
			F += G
		if F > G:
			F = G
		if F <= C:
			raise E(L.format(D))
		K = H._maxes
		I = bisect_left(K, D)
		if I == A(K):
			raise E(L.format(D))
		M = H._lists
		N = bisect_left(M[I], D)
		if M[I][N] != D:
			raise E(L.format(D))
		F -= 1
		J = H._loc(I, N)
		if C <= J:
			if J <= F:
				return J
		else:
			O = H._bisect_right(D) - 1
			if C <= O:
				return C
		raise E(L.format(D))

	def __add__(A, other):
		B = G(F, A._lists, [])
		B.extend(other)
		return A.__class__(B)
	__radd__ = __add__

	def __iadd__(A, other):
		A._update(other)
		return A

	def __mul__(A, num):
		B = G(F, A._lists, []) * num
		return A.__class__(B)
	__rmul__ = __mul__

	def __imul__(A, num):
		B = G(F, A._lists, []) * num
		A._clear()
		A._update(B)
		return A

	def __make_cmp(B, symbol, doc):

		def C(self, other):
			C = other
			if not b(C, Sequence):
				return NotImplemented
			D = self._len
			E = A(C)
			if D != E:
				if B is eq:
					return K
				if B is ne:
					return I
			for (F, G) in zip(self, C):
				if F != G:
					return B(F, G)
			return B(D, E)
		D = B.__name__
		C.__name__ = '__{0}__'.format(D)
		E = 'Return true if and only if sorted list is {0} `other`.\n\n        ``sl.__{1}__(other)`` <==> ``sl {2} other``\n\n        Comparisons use lexicographical order as with sequences.\n\n        Runtime complexity: `O(n)`\n\n        :param other: `other` sequence\n        :return: true if sorted list is {0} `other`\n\n        '
		C.__doc__ = f(E.format(doc, D, symbol))
		return C
	__eq__ = __make_cmp(eq, '==', 'equal to')
	__ne__ = __make_cmp(ne, '!=', 'not equal to')
	__lt__ = __make_cmp(lt, '<', 'less than')
	__gt__ = __make_cmp(gt, '>', 'greater than')
	__le__ = __make_cmp(le, '<=', 'less than or equal to')
	__ge__ = __make_cmp(ge, '>=', 'greater than or equal to')
	__make_cmp = staticmethod(__make_cmp)

	def __reduce__(A):
		B = G(F, A._lists, [])
		return (S(A), (B,))

	@W()
	def __repr__(self):
		return '{0}({1!r})'.format(S(self).__name__, N(self))

	def _check(B):
		try:
			assert B._load >= 4
			assert A(B._maxes) == A(B._lists)
			assert B._len == j((A(C) for C in B._lists))
			for G in B._lists:
				for E in C(1, A(G)):
					assert G[E - 1] <= G[E]
			for E in C(1, A(B._lists)):
				assert B._lists[E - 1][-1] <= B._lists[E][0]
			for E in C(A(B._maxes)):
				assert B._maxes[E] == B._lists[E][-1]
			H = B._load << 1
			assert k((A(C) <= H for C in B._lists))
			I = B._load >> 1
			for E in C(0, A(B._lists) - 1):
				assert A(B._lists[E]) >= I
			if B._index:
				assert B._len == B._index[0]
				assert A(B._index) == B._offset + A(B._lists)
				for E in C(A(B._lists)):
					J = B._index[B._offset + E]
					assert J == A(B._lists[E])
				for E in C(B._offset):
					F = (E << 1) + 1
					if F >= A(B._index):
						assert B._index[E] == 0
					elif F + 1 == A(B._index):
						assert B._index[E] == B._index[F]
					else:
						K = B._index[F] + B._index[F + 1]
						assert K == B._index[E]
		except:
			T.print_exc(file=sys.stdout)
			D(m, B._len)
			D(n, B._load)
			D(o, B._offset)
			D(p, A(B._index))
			D(q, B._index)
			D(r, A(B._maxes))
			D(s, B._maxes)
			D(t, A(B._lists))
			D(u, B._lists)
			raise

def Y(value):
	return value

class Z(X):

	def __init__(A, iterable=B, key=Y):
		C = iterable
		A._key = key
		A._len = 0
		A._load = A.DEFAULT_LOAD_FACTOR
		A._lists = []
		A._keys = []
		A._maxes = []
		A._index = []
		A._offset = 0
		if C is not B:
			A._update(C)

	def __new__(A, iterable=B, key=Y):
		return object.__new__(A)

	@h
	def key(self):
		return self._key

	def clear(A):
		A._len = 0
		del A._lists[:]
		del A._keys[:]
		del A._maxes[:]
		del A._index[:]
	_clear = clear

	def add(D, value):
		F = value
		H = D._lists
		G = D._keys
		E = D._maxes
		C = D._key(F)
		if E:
			B = bisect_right(E, C)
			if B == A(E):
				B -= 1
				H[B].append(F)
				G[B].append(C)
				E[B] = C
			else:
				I = bisect_right(G[B], C)
				H[B].insert(I, F)
				G[B].insert(I, C)
			D._expand(B)
		else:
			H.append([F])
			G.append([C])
			E.append(C)
		D._len += 1

	def _expand(C, pos):
		B = pos
		I = C._lists
		G = C._keys
		D = C._index
		if A(G[B]) > C._load << 1:
			J = C._maxes
			E = C._load
			K = I[B]
			H = G[B]
			M = K[E:]
			L = H[E:]
			del K[E:]
			del H[E:]
			J[B] = H[-1]
			I.insert(B + 1, M)
			G.insert(B + 1, L)
			J.insert(B + 1, L[-1])
			del D[:]
		elif D:
			F = C._offset + B
			while F:
				D[F] += 1
				F = F - 1 >> 1
			D[0] += 1

	def update(B, iterable):
		E = B._lists
		H = B._keys
		I = B._maxes
		D = i(iterable, key=B._key)
		if I:
			if A(D) * 4 >= B._len:
				E.append(D)
				D = G(F, E, [])
				D.sort(key=B._key)
				B._clear()
			else:
				K = B.add
				for L in D:
					K(L)
				return
		J = B._load
		E.extend((D[B:B + J] for B in C(0, A(D), J)))
		H.extend((N(map(B._key, A)) for A in E))
		I.extend((A[-1] for A in H))
		B._len = A(D)
		del B._index[:]
	_update = update

	def __contains__(E, value):
		H = value
		F = E._maxes
		if not F:
			return K
		G = E._key(H)
		B = bisect_left(F, G)
		if B == A(F):
			return K
		L = E._lists
		C = E._keys
		D = bisect_left(C[B], G)
		M = A(C)
		J = A(C[B])
		while I:
			if C[B][D] != G:
				return K
			if L[B][D] == H:
				return I
			D += 1
			if D == J:
				B += 1
				if B == M:
					return K
				J = A(C[B])
				D = 0

	def discard(D, value):
		H = value
		F = D._maxes
		if not F:
			return
		G = D._key(H)
		B = bisect_left(F, G)
		if B == A(F):
			return
		K = D._lists
		E = D._keys
		C = bisect_left(E[B], G)
		L = A(E)
		J = A(E[B])
		while I:
			if E[B][C] != G:
				return
			if K[B][C] == H:
				D._delete(B, C)
				return
			C += 1
			if C == J:
				B += 1
				if B == L:
					return
				J = A(E[B])
				C = 0

	def remove(F, value):
		C = value
		H = F._maxes
		if not H:
			raise E(O.format(C))
		J = F._key(C)
		B = bisect_left(H, J)
		if B == A(H):
			raise E(O.format(C))
		L = F._lists
		G = F._keys
		D = bisect_left(G[B], J)
		M = A(G)
		K = A(G[B])
		while I:
			if G[B][D] != J:
				raise E(O.format(C))
			if L[B][D] == C:
				F._delete(B, D)
				return
			D += 1
			if D == K:
				B += 1
				if B == M:
					raise E(O.format(C))
				K = A(G[B])
				D = 0

	def _delete(C, pos, idx):
		B = pos
		E = C._lists
		D = C._keys
		F = C._maxes
		G = C._index
		I = D[B]
		L = E[B]
		del I[idx]
		del L[idx]
		C._len -= 1
		K = A(I)
		if K > C._load >> 1:
			F[B] = I[-1]
			if G:
				J = C._offset + B
				while J > 0:
					G[J] -= 1
					J = J - 1 >> 1
				G[0] -= 1
		elif A(D) > 1:
			if not B:
				B += 1
			H = B - 1
			D[H].extend(D[B])
			E[H].extend(E[B])
			F[H] = D[H][-1]
			del E[B]
			del D[B]
			del F[B]
			del G[:]
			C._expand(H)
		elif K:
			F[B] = I[-1]
		else:
			del E[B]
			del D[B]
			del F[B]
			del G[:]

	def irange(A, minimum=B, maximum=B, inclusive=(I, I), reverse=K):
		D = maximum
		C = minimum
		E = A._key(C) if C is not B else B
		F = A._key(D) if D is not B else B
		return A._irange_key(min_key=E, max_key=F, inclusive=inclusive, reverse=reverse)

	def irange_key(K, min_key=B, max_key=B, inclusive=(I, I), reverse=K):
		M = inclusive
		I = max_key
		G = min_key
		D = K._maxes
		if not D:
			return H(())
		E = K._keys
		if G is B:
			F = 0
			L = 0
		elif M[0]:
			F = bisect_left(D, G)
			if F == A(D):
				return H(())
			L = bisect_left(E[F], G)
		else:
			F = bisect_right(D, G)
			if F == A(D):
				return H(())
			L = bisect_right(E[F], G)
		if I is B:
			C = A(D) - 1
			J = A(E[C])
		elif M[1]:
			C = bisect_right(D, I)
			if C == A(D):
				C -= 1
				J = A(E[C])
			else:
				J = bisect_right(E[C], I)
		else:
			C = bisect_left(D, I)
			if C == A(D):
				C -= 1
				J = A(E[C])
			else:
				J = bisect_left(E[C], I)
		return K._islice(F, L, C, J, reverse)
	_irange_key = irange_key

	def bisect_left(A, value):
		return A._bisect_key_left(A._key(value))

	def bisect_right(A, value):
		return A._bisect_key_right(A._key(value))
	bisect = bisect_right

	def bisect_key_left(B, key):
		C = B._maxes
		if not C:
			return 0
		D = bisect_left(C, key)
		if D == A(C):
			return B._len
		E = bisect_left(B._keys[D], key)
		return B._loc(D, E)
	_bisect_key_left = bisect_key_left

	def bisect_key_right(B, key):
		C = B._maxes
		if not C:
			return 0
		D = bisect_right(C, key)
		if D == A(C):
			return B._len
		E = bisect_right(B._keys[D], key)
		return B._loc(D, E)
	bisect_key = bisect_key_right
	_bisect_key_right = bisect_key_right

	def count(E, value):
		J = value
		F = E._maxes
		if not F:
			return 0
		G = E._key(J)
		B = bisect_left(F, G)
		if B == A(F):
			return 0
		L = E._lists
		C = E._keys
		D = bisect_left(C[B], G)
		H = 0
		M = A(C)
		K = A(C[B])
		while I:
			if C[B][D] != G:
				return H
			if L[B][D] == J:
				H += 1
			D += 1
			if D == K:
				B += 1
				if B == M:
					return H
				K = A(C[B])
				D = 0

	def copy(A):
		return A.__class__(A, key=A._key)
	__copy__ = copy

	def index(H, value, start=B, stop=B):
		G = start
		F = value
		C = stop
		J = H._len
		if not J:
			raise E(L.format(F))
		if G is B:
			G = 0
		if G < 0:
			G += J
		if G < 0:
			G = 0
		if C is B:
			C = J
		if C < 0:
			C += J
		if C > J:
			C = J
		if C <= G:
			raise E(L.format(F))
		P = H._maxes
		N = H._key(F)
		D = bisect_left(P, N)
		if D == A(P):
			raise E(L.format(F))
		C -= 1
		R = H._lists
		M = H._keys
		K = bisect_left(M[D], N)
		S = A(M)
		Q = A(M[D])
		while I:
			if M[D][K] != N:
				raise E(L.format(F))
			if R[D][K] == F:
				O = H._loc(D, K)
				if G <= O <= C:
					return O
				elif O > C:
					break
			K += 1
			if K == Q:
				D += 1
				if D == S:
					raise E(L.format(F))
				Q = A(M[D])
				K = 0
		raise E(L.format(F))

	def __add__(A, other):
		B = G(F, A._lists, [])
		B.extend(other)
		return A.__class__(B, key=A._key)
	__radd__ = __add__

	def __mul__(A, num):
		B = G(F, A._lists, []) * num
		return A.__class__(B, key=A._key)

	def __reduce__(A):
		B = G(F, A._lists, [])
		return (S(A), (B, A.key))

	@W()
	def __repr__(self):
		A = self
		B = S(A).__name__
		return '{0}({1!r}, key={2!r})'.format(B, N(A), A._key)

	def _check(B):
		try:
			assert B._load >= 4
			assert A(B._maxes) == A(B._lists) == A(B._keys)
			assert B._len == j((A(C) for C in B._lists))
			for G in B._keys:
				for E in C(1, A(G)):
					assert G[E - 1] <= G[E]
			for E in C(1, A(B._keys)):
				assert B._keys[E - 1][-1] <= B._keys[E][0]
			for (H, I) in zip(B._lists, B._keys):
				assert A(H) == A(I)
				for (J, K) in zip(H, I):
					assert B._key(J) == K
			for E in C(A(B._maxes)):
				assert B._maxes[E] == B._keys[E][-1]
			L = B._load << 1
			assert k((A(C) <= L for C in B._lists))
			M = B._load >> 1
			for E in C(0, A(B._lists) - 1):
				assert A(B._lists[E]) >= M
			if B._index:
				assert B._len == B._index[0]
				assert A(B._index) == B._offset + A(B._lists)
				for E in C(A(B._lists)):
					N = B._index[B._offset + E]
					assert N == A(B._lists[E])
				for E in C(B._offset):
					F = (E << 1) + 1
					if F >= A(B._index):
						assert B._index[E] == 0
					elif F + 1 == A(B._index):
						assert B._index[E] == B._index[F]
					else:
						O = B._index[F] + B._index[F + 1]
						assert O == B._index[E]
		except:
			T.print_exc(file=sys.stdout)
			D(m, B._len)
			D(n, B._load)
			D(o, B._offset)
			D(p, A(B._index))
			D(q, B._index)
			D(r, A(B._maxes))
			D(s, B._maxes)
			D('len_keys', A(B._keys))
			D('keys', B._keys)
			D(t, A(B._lists))
			D(u, B._lists)
			raise
v = Z
import sys
sys.setrecursionlimit(100000)

def _r():
	return sys.stdin.buffer.readline()

def rs():
	return _r().decode('ascii').strip()

def rn():
	return int(_r())

def rnt():
	return map(int, _r().split())

def rnl():
	return list(rnt())

def solve(n, a):
	d = X()
	total = 0
	for x in a:
		l = d.bisect_left(x)
		r = d.bisect_right(x)
		total += min(l, len(d) - r)
		d.add(x)
	return total
for _ in range(rn()):
	n = rn()
	a = rnl()
	print(solve(n, a))


def naiveSolve():
	return

def solve():
	return

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))

class OrderedList(SortedList):

	def __init__(self, arg):
		super().__init__(arg)

	def rangeCountByValue(self, leftVal, rightVal):
		leftCummulative = self.bisect_left(leftVal)
		rightCummulative = self.bisect_left(rightVal + 1)
		return rightCummulative - leftCummulative

def main():
	t = int(input())
	allans = []
	for _ in range(t):
		n = int(input())
		a = readIntArr()
		sl = SortedList([])
		ans = 0
		for x in a:
			sl.add(x)
			left = sl.bisect_left(x)
			right = len(sl) - sl.bisect_right(x)
			ans += min(left, right)
		allans.append(ans)
	multiLineArrayPrint(allans)
	return
import sys
input = sys.stdin.buffer.readline

def oneLineArrayPrint(arr):
	print(' '.join([str(x) for x in arr]))

def multiLineArrayPrint(arr):
	print('\n'.join([str(x) for x in arr]))

def multiLineArrayOfArraysPrint(arr):
	print('\n'.join([' '.join([str(x) for x in y]) for y in arr]))

def readIntArr():
	return [int(x) for x in input().split()]

def makeArr(defaultValFactory, dimensionArr):
	dv = defaultValFactory
	da = dimensionArr
	if len(da) == 1:
		return [dv() for _ in range(da[0])]
	else:
		return [makeArr(dv, da[1:]) for _ in range(da[0])]

def queryInteractive(x):
	print('{}'.format(x))
	sys.stdout.flush()
	return int(input())

def answerInteractive(ans):
	print('! {}'.format(ans))
	sys.stdout.flush()
inf = float('inf')
from math import gcd, floor, ceil
for _abc in range(1):
	main()


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
t = int(input())

def less(arr, start, end):
	ans = -1
	while start <= end:
		mid = (start + end) // 2
		if arr[mid] < k:
			ans = mid
			start = mid + 1
		else:
			end = mid - 1
	return ans + 1

def greater(arr, start, end):
	ans = -1
	while start <= end:
		mid = (start + end) // 2
		if arr[mid] > k:
			ans = mid
			end = mid - 1
		else:
			start = mid + 1
	if ans == -1:
		return 0
	return len(arr) - ans

def bs1(arr, start, end):
	ans = -1
	while start <= end:
		mid = (start + end) // 2
		if arr[mid] <= k:
			ans = mid
			start = mid + 1
		else:
			end = mid - 1
	return ans + 1

class segment_tree_mergesort:

	def __init__(self, arr):
		self.arr = arr
		self.l = len(arr)
		import math
		h = math.floor(math.log2(self.l) + 1)
		self.st = [[] for x in range(2 ** (h + 1) + 1)]
		self.si = 1
		self.ss = 0
		self.se = self.l - 1
		self.__buildmintree(self.si, self.ss, self.se)

	def __buildmintree(self, si, ss, se):
		if ss == se:
			self.st[si] = [self.arr[ss]]
			return True
		mid = (ss + se) // 2
		self.__buildmintree(2 * si, ss, mid)
		self.__buildmintree(2 * si + 1, mid + 1, se)
		i = 0
		j = 0
		while i < len(self.st[2 * si]) and j < len(self.st[2 * si + 1]):
			if self.st[2 * si][i] <= self.st[2 * si + 1][j]:
				self.st[si].append(self.st[2 * si][i])
				i += 1
			else:
				self.st[si].append(self.st[2 * si + 1][j])
				j += 1
		while i < len(self.st[2 * si]):
			self.st[si].append(self.st[2 * si][i])
			i += 1
		while j < len(self.st[2 * si + 1]):
			self.st[si].append(self.st[2 * si + 1][j])
			j += 1

	def query(self, si, ss, se, qs, qe, type):
		if se < qs or qe < ss:
			return 0
		if qs <= ss and se <= qe:
			if type == 1:
				return less(self.st[si], 0, len(self.st[si]) - 1)
			else:
				return greater(self.st[si], 0, len(self.st[si]) - 1)
		mid = (ss + se) // 2
		l = self.query(2 * si, ss, mid, qs, qe, type)
		r = self.query(2 * si + 1, mid + 1, se, qs, qe, type)
		return l + r
while t:
	t -= 1
	n = int(input())
	arr = [int(x) for x in input().split()]
	d = {}
	count = [0 for x in range(n)]
	for i in range(n):
		if arr[i] not in d:
			d[arr[i]] = 1
			count[i] = d[arr[i]]
		else:
			d[arr[i]] += 1
			count[i] = d[arr[i]]
	s = segment_tree_mergesort(arr)
	res = 0
	for i in range(1, n):
		k = arr[i]
		l = s.query(1, 0, n - 1, 0, i - 1, 1)
		g = i - l - count[i] + 1
		res += min(l, g)
	sys.stdout.write(f'{res}\n')


try:
	import sys
	from functools import lru_cache, cmp_to_key
	from heapq import merge, heapify, heappop, heappush
	from collections import defaultdict as dd, deque, Counter as C
	from itertools import combinations as comb, permutations as perm
	from bisect import bisect_left as bl, bisect_right as br, bisect, insort
	from time import perf_counter
	from fractions import Fraction
	import copy
	from copy import deepcopy
	import time
	starttime = time.time()
	mod = int(pow(10, 9) + 7)
	mod2 = 998244353

	def data():
		return sys.stdin.readline().strip()

	def out(*var, end='\n'):
		sys.stdout.write(' '.join(map(str, var)) + end)

	def L():
		return list(sp())

	def sl():
		return list(ssp())

	def sp():
		return map(int, data().split())

	def ssp():
		return map(str, data().split())

	def l1d(n, val=0):
		return [val for i in range(n)]

	def l2d(n, m, val=0):
		return [l1d(n, val) for j in range(m)]

	def A2(n, m):
		return [[0] * m for i in range(n)]

	def A(n):
		return [0] * n
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
except:
	pass
for _ in range(L()[0]):
	n = L()[0]
	A = L()
	rank = {}
	for (i, v) in enumerate(sorted(A)):
		rank[v] = i + 1
	A = [rank[ele] for ele in A]
	BIT = [0 for i in range(n + 10)]

	def update(i):
		while i <= n:
			BIT[i] += 1
			i += i & -i

	def get_sum(i):
		s = 0
		while i:
			s += BIT[i]
			i -= i & -i
		return s
	q = deque()
	q.append(A[0])
	update(A[0])
	cnt = 1
	ans = 0
	for ele in A[1:]:
		x1 = get_sum(ele - 1)
		x2 = get_sum(ele)
		if x1 < cnt - x2:
			q.appendleft(ele)
			ans += x1
			update(ele)
		else:
			q.append(ele)
			ans += cnt - x2
			update(ele)
		cnt += 1
	print(ans)


from collections import defaultdict, deque, Counter
from heapq import heapify, heappop, heappush
import math
from copy import deepcopy
from itertools import combinations, permutations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
import sys

def input():
	return sys.stdin.readline().rstrip()

def getN():
	return int(input())

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

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

def getListGraph():
	return list(map(lambda x: int(x) - 1, input().split()))

def getArray(intn):
	return [int(input()) for i in range(intn)]
mod = 10 ** 9 + 7
MOD = 998244353
inf = float('inf')
eps = 10 ** (-10)
dy = [0, 1, 0, -1]
dx = [1, 0, -1, 0]

class Comp_BIT:

	def __init__(self, N, array):
		self.N = N
		self.bit = [0] * (N + 1)
		self.b = 1 << N.bit_length() - 1
		s = set(array)
		s = sorted(list(s))
		self.alter = {}
		self.rev = {}
		for i in range(len(s)):
			self.alter[s[i]] = i + 1
			self.rev[i + 1] = s[i]

	def add(self, a, w):
		x = self.alter[a]
		while x <= self.N:
			self.bit[x] += w
			x += x & -x

	def get(self, a):
		(ret, x) = (0, self.alter[a] - 1)
		while x > 0:
			ret += self.bit[x]
			x -= x & -x
		return ret

	def get_rig(self, a):
		(ret, x) = (0, self.alter[a])
		while x > 0:
			ret += self.bit[x]
			x -= x & -x
		return ret

	def cum(self, l, r):
		return self.get(r) - self.get(l)

	def lowerbound(self, w):
		if w <= 0:
			return 0
		x = 0
		k = self.b
		while k > 0:
			if x + k <= self.N and self.bit[x + k] < w:
				w -= self.bit[x + k]
				x += k
			k //= 2
		return self.rev[x + 1]
T = getN()
for _ in range(T):
	N = getN()
	A = getList()
	code = sorted(list(set(A)))
	bit = Comp_BIT(len(code), code)
	ans = 0
	for i in range(N):
		bit.add(A[i], 1)
		ans += min(bit.get(A[i]), i + 1 - bit.get_rig(A[i]))
	print(ans)


from __future__ import print_function
from math import *
from collections import deque
import os
import sys
from io import BytesIO, IOBase

def main():
	pass
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
mod = 10 ** 9 + 7

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))

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

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

def insr():
	s = input()
	return list(s[:len(s)])

def invr():
	return map(int, input().split())
for _ in range(inp()):
	n = inp()
	l = inlt()
	c = 0
	q = deque()
	q.append(l[0])
	s = SortedList()
	s.add(l[0])
	for i in range(1, n):
		a = s.bisect_right(l[i])
		right = len(s) - a
		a = s.bisect_left(l[i])
		left = a
		if left < right:
			q.append(l[i])
			s.add(l[i])
			c += left
		else:
			q.appendleft(l[i])
			s.add(l[i])
			c += right
	print(c)


class FenwickTree:

	def __init__(self, n):
		self.n = n
		self.f = [0] * (n + 1)

	def update(self, x, d):
		while x <= self.n:
			self.f[x] += d
			x += x & -x

	def prefix(self, x):
		ans = 0
		while x:
			ans += self.f[x]
			x &= x - 1
		return ans

def lower_bound(a, x):
	l = 0
	r = len(a)
	while l < r:
		mid = l + r >> 1
		if a[mid] >= x:
			r = mid
		else:
			l = mid + 1
	return r

def upper_bound(a, x):
	l = 0
	r = len(a)
	while l < r:
		mid = l + r >> 1
		if a[mid] > x:
			r = mid
		else:
			l = mid + 1
	return r
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = sorted(a)
	for i in range(n):
		a[i] = lower_bound(b, a[i]) + 1
	f = FenwickTree(n)
	ans = 0
	for i in range(n):
		x = f.prefix(a[i] - 1)
		y = f.prefix(a[i])
		ans += min(x, i - y)
		f.update(a[i], 1)
	print(ans)


import sys
import math
import heapq
import bisect
from collections import Counter
from collections import defaultdict, deque
from io import BytesIO, IOBase
from itertools import permutations
import string

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		import os
		self.os = os
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None
		self.BUFSIZE = 8192

	def read(self):
		while True:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, self.BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			self.os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

def get_int():
	return int(input())

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

def get_int_grid(n):
	return [get_ints() for _ in range(n)]

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

def get_strs():
	return get_str().split(' ')

def flat_list(arr):
	return [item for subarr in arr for item in subarr]

def yes_no(b):
	if b:
		return 'YES'
	else:
		return 'NO'

def binary_search(good, left, right, delta=1, right_true=False):
	limits = [left, right]
	while limits[1] - limits[0] > delta:
		if delta == 1:
			mid = sum(limits) // 2
		else:
			mid = sum(limits) / 2
		if good(mid):
			limits[int(right_true)] = mid
		else:
			limits[int(~right_true)] = mid
	if good(limits[int(right_true)]):
		return limits[int(right_true)]
	else:
		return False

def prefix_sums(a):
	p = [0]
	for x in a:
		p.append(p[-1] + x)
	return p

class SortedList:

	def __init__(self, iterable=[], _load=200):
		values = sorted(iterable)
		self._len = _len = len(values)
		self._load = _load
		self._lists = _lists = [values[i:i + _load] for i in range(0, _len, _load)]
		self._list_lens = [len(_list) for _list in _lists]
		self._mins = [_list[0] for _list in _lists]
		self._fen_tree = []
		self._rebuild = True

	def _fen_build(self):
		self._fen_tree[:] = self._list_lens
		_fen_tree = self._fen_tree
		for i in range(len(_fen_tree)):
			if i | i + 1 < len(_fen_tree):
				_fen_tree[i | i + 1] += _fen_tree[i]
		self._rebuild = False

	def _fen_update(self, index, value):
		if not self._rebuild:
			_fen_tree = self._fen_tree
			while index < len(_fen_tree):
				_fen_tree[index] += value
				index |= index + 1

	def _fen_query(self, end):
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		x = 0
		while end:
			x += _fen_tree[end - 1]
			end &= end - 1
		return x

	def _fen_findkth(self, k):
		_list_lens = self._list_lens
		if k < _list_lens[0]:
			return (0, k)
		if k >= self._len - _list_lens[-1]:
			return (len(_list_lens) - 1, k + _list_lens[-1] - self._len)
		if self._rebuild:
			self._fen_build()
		_fen_tree = self._fen_tree
		idx = -1
		for d in reversed(range(len(_fen_tree).bit_length())):
			right_idx = idx + (1 << d)
			if right_idx < len(_fen_tree) and k >= _fen_tree[right_idx]:
				idx = right_idx
				k -= _fen_tree[idx]
		return (idx + 1, k)

	def _delete(self, pos, idx):
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len -= 1
		self._fen_update(pos, -1)
		del _lists[pos][idx]
		_list_lens[pos] -= 1
		if _list_lens[pos]:
			_mins[pos] = _lists[pos][0]
		else:
			del _lists[pos]
			del _list_lens[pos]
			del _mins[pos]
			self._rebuild = True

	def _loc_left(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(lo, pos) = (-1, len(_lists) - 1)
		while lo + 1 < pos:
			mi = lo + pos >> 1
			if value <= _mins[mi]:
				pos = mi
			else:
				lo = mi
		if pos and value <= _lists[pos - 1][-1]:
			pos -= 1
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value <= _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def _loc_right(self, value):
		if not self._len:
			return (0, 0)
		_lists = self._lists
		_mins = self._mins
		(pos, hi) = (0, len(_lists))
		while pos + 1 < hi:
			mi = pos + hi >> 1
			if value < _mins[mi]:
				hi = mi
			else:
				pos = mi
		_list = _lists[pos]
		(lo, idx) = (-1, len(_list))
		while lo + 1 < idx:
			mi = lo + idx >> 1
			if value < _list[mi]:
				idx = mi
			else:
				lo = mi
		return (pos, idx)

	def add(self, value):
		_load = self._load
		_lists = self._lists
		_mins = self._mins
		_list_lens = self._list_lens
		self._len += 1
		if _lists:
			(pos, idx) = self._loc_right(value)
			self._fen_update(pos, 1)
			_list = _lists[pos]
			_list.insert(idx, value)
			_list_lens[pos] += 1
			_mins[pos] = _list[0]
			if _load + _load < len(_list):
				_lists.insert(pos + 1, _list[_load:])
				_list_lens.insert(pos + 1, len(_list) - _load)
				_mins.insert(pos + 1, _list[_load])
				_list_lens[pos] = _load
				del _list[_load:]
				self._rebuild = True
		else:
			_lists.append([value])
			_mins.append(value)
			_list_lens.append(1)
			self._rebuild = True

	def discard(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_right(value)
			if idx and _lists[pos][idx - 1] == value:
				self._delete(pos, idx - 1)

	def remove(self, value):
		_len = self._len
		self.discard(value)
		if _len == self._len:
			raise ValueError('{0!r} not in list'.format(value))

	def pop(self, index=-1):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		value = self._lists[pos][idx]
		self._delete(pos, idx)
		return value

	def bisect_left(self, value):
		(pos, idx) = self._loc_left(value)
		return self._fen_query(pos) + idx

	def bisect_right(self, value):
		(pos, idx) = self._loc_right(value)
		return self._fen_query(pos) + idx

	def count(self, value):
		return self.bisect_right(value) - self.bisect_left(value)

	def __len__(self):
		return self._len

	def __getitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		return self._lists[pos][idx]

	def __delitem__(self, index):
		(pos, idx) = self._fen_findkth(self._len + index if index < 0 else index)
		self._delete(pos, idx)

	def __contains__(self, value):
		_lists = self._lists
		if _lists:
			(pos, idx) = self._loc_left(value)
			return idx < len(_lists[pos]) and _lists[pos][idx] == value
		return False

	def __iter__(self):
		return (value for _list in self._lists for value in _list)

	def __reversed__(self):
		return (value for _list in reversed(self._lists) for value in reversed(_list))

	def __repr__(self):
		return 'SortedList({0})'.format(list(self))

def solve_e2():
	n = get_int()
	a = get_ints()
	SL = SortedList([])
	cnt = 0
	for (i, x) in enumerate(a):
		l = SL.bisect_left(x)
		r = i - SL.bisect_right(x)
		cnt += min(l, r)
		SL.add(x)
	return cnt
t = get_int()
for _ in range(t):
	print(solve_e2())


import sys
input = sys.stdin.readline
from collections import *

def compress(l):
	l = list(set(l))
	l.sort()
	idx = defaultdict(int)
	for i in range(len(l)):
		idx[l[i]] = i
	return idx

class BIT:

	def __init__(self, n):
		self.n = n
		self.bit = [0] * (n + 1)

	def add(self, i, x):
		i += 1
		while i <= self.n:
			self.bit[i] += x
			i += i & -i

	def acc(self, i):
		s = 0
		while i > 0:
			s += self.bit[i]
			i -= i & -i
		return s
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	idx = compress(a)
	m = len(idx.keys())
	bit = BIT(m)
	ans = 0
	for ai in a:
		l = bit.acc(m) - bit.acc(idx[ai] + 1)
		r = bit.acc(idx[ai])
		ans += min(l, r)
		bit.add(idx[ai], 1)
	print(ans)


import sys
from bisect import bisect_right as lb
from collections import deque
from queue import PriorityQueue as pq
from math import gcd
input_ = lambda : sys.stdin.readline().strip('\r\n')
ii = lambda : int(input_())
il = lambda : list(map(int, input_().split()))
ilf = lambda : list(map(float, input_().split()))
lii = lambda : list(map(int, list(ip())))
ip = lambda : input_()
fi = lambda : float(input_())
ap = lambda ab, bc, cd: ab[bc].append(cd)
li = lambda : list(input_())
pr = lambda x: print(x)
prinT = lambda x: print(x)
f = lambda : sys.stdout.flush()
inv = lambda x: pow(x, mod - 2, mod)
mod = 10 ** 9 + 7

def get(bit, i):
	ans = 0
	while i > 0:
		ans += bit[i]
		i -= i & -i
	return ans

def upd(bit, i, a):
	while i < len(bit):
		bit[i] += 1
		i += i & -i
for _ in range(ii()):
	n = ii()
	a = il()
	b = [i for i in a]
	b.sort()
	d = {}
	for i in range(n):
		if d.get(b[i]) is not None:
			continue
		d[b[i]] = i + 1
	for i in range(n):
		a[i] = d[a[i]]
	bit = [0 for i in range(n + 2)]
	ans = 0
	for i in range(n):
		ans += min(get(bit, a[i] - 1), i - get(bit, a[i]))
		upd(bit, a[i], 1)
	print(ans)


import sys
input = sys.stdin.readline

def get_merge(l, r, n, a, res):
	if l == r:
		return [l]
	mid = (l + r) // 2
	left = get_merge(l, mid, n, a, res)
	right = get_merge(mid + 1, r, n, a, res)
	ind = []
	while True:
		if left and right:
			if a[left[-1]] > a[right[-1]]:
				res[left[-1]] += len(right)
				ind.append(left.pop())
			else:
				ind.append(right.pop())
		elif not right and left:
			ind.append(left.pop())
		elif not left and right:
			ind.append(right.pop())
		else:
			break
	return ind[::-1]
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	smaller_ = [0] * n
	get_merge(0, n - 1, n, a[::-1], smaller_)
	smaller_ = smaller_[::-1]
	larger_ = [0] * n
	for i in range(n):
		a[i] = -1 * a[i]
	get_merge(0, n - 1, n, a[::-1], larger_)
	larger_ = larger_[::-1]
	ans = 0
	for i in range(n):
		ans += min(smaller_[i], larger_[i])
	print(ans)


Q = int(input())

class BIT:

	def __init__(self, n, op=lambda x, y: x + y, inv=lambda x: -x, ie=0):
		self.n = n
		self.op = op
		self.ie = ie
		self.inv = inv
		self.el = [ie] * (n + 1)
		self.data = [ie] * (n + 1)

	def add(self, i, x):
		op = self.op
		self.el[i] = op(self.el[i], x)
		data = self.data
		while i <= self.n:
			data[i] = op(data[i], x)
			i += i & -i

	def _obtain(self, i):
		data = self.data
		op = self.op
		ans = 0
		while i > 0:
			ans = op(data[i], ans)
			i -= i & -i
		return ans

	def apply(self, l, r):
		return self.op(self.inv(self._obtain(l - 1)), self._obtain(r - 1))

	def construct(self, A):
		for (i, x) in enumerate(A):
			self.add(i + 1, x)
from collections import defaultdict as dft

def main():
	N = int(input())
	A = list(map(int, input().split()))
	A_set = set(A)
	A_list = list(A_set)
	A_list.sort()
	A_inv = dft(int)
	for (i, a) in enumerate(A_list):
		A_inv[a] = i + 1
	M = len(A_inv)
	bt = BIT(M)
	ans = 0
	for a in A:
		a_id = A_inv[a]
		inv_l = bt.apply(1, a_id)
		inv_r = bt.apply(a_id + 1, M + 1)
		ans += min(inv_l, inv_r)
		bt.add(a_id, 1)
	print(ans)
for _ in range(Q):
	main()


import sys
INF = float('inf')
mod = 998244353
input = lambda : sys.stdin.readline().rstrip()

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

class BIT:

	def __init__(self, n):
		self.size = n
		self.tree = [0] * (n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.tree[i]
			i -= i & -i
		return s

	def range_sum(self, l, r):
		if l == 1:
			return self.sum(r)
		else:
			return self.sum(r) - self.sum(l - 1)

	def add(self, i, x):
		while i <= self.size:
			self.tree[i] += x
			i += i & -i
from collections import deque
T = int(input())
for _ in range(T):
	N = int(input())
	A = li()
	sortedA = set(sorted(A))
	dic = {a: e + 2 for (e, a) in enumerate(sortedA)}
	bit = BIT(N + 5)
	dq = deque()
	dq.append(dic[A[0]])
	bit.add(dic[A[0]], 1)
	for i in range(1, N):
		a = dic[A[i]]
		upper = bit.range_sum(a + 1, N + 3)
		lower = bit.sum(a - 1)
		if upper > lower:
			dq.appendleft(a)
		else:
			dq.append(a)
		bit.add(a, 1)
	bit2 = BIT(N + 5)
	ans = 0
	for i in range(N):
		x = dq.popleft()
		ans += i - bit2.sum(x + 1)
		bit2.add(x + 1, 1)
	print(ans)


class FenwickTree:

	def __init__(self, a):
		self.bit = [0] * len(a)
		for (i, x) in enumerate(a):
			if x:
				self.add(i, x)

	def query(self, i):
		s = 0
		bit = self.bit
		while i >= 0:
			s += bit[i]
			i = (i & i + 1) - 1
		return s

	def add(self, i, delta=1):
		n = len(self.bit)
		bit = self.bit
		while i < n:
			bit[i] += delta
			i |= i + 1
for _ in range(int(input())):
	input()
	a = list(map(int, input().split()))
	order = {}
	i = 0
	for x in sorted(a):
		if x not in order:
			order[x] = i
			i += 1
	inversions = 0
	tree = FenwickTree([0] * len(order))
	for (i, k) in enumerate(map(order.__getitem__, a)):
		inversions += min(tree.query(k - 1), i - tree.query(k))
		tree.add(k)
	print(inversions)


import sys
import traceback
from bisect import bisect_left, bisect_right, insort
from itertools import chain, repeat, starmap
from math import log
from operator import add, eq, ne, gt, ge, lt, le, iadd
from collections.abc import Sequence, MutableSequence
from functools import wraps
from functools import reduce
from _thread import get_ident

def recursive_repr(fillvalue='...'):

	def decorating_function(user_function):
		repr_running = set()

		@wraps(user_function)
		def wrapper(self):
			key = (id(self), get_ident())
			if key in repr_running:
				return fillvalue
			repr_running.add(key)
			try:
				result = user_function(self)
			finally:
				repr_running.discard(key)
			return result
		return wrapper
	return decorating_function

class SortedList(MutableSequence):
	DEFAULT_LOAD_FACTOR = 1000

	def __init__(self, iterable=None):
		self._len = 0
		self._load = self.DEFAULT_LOAD_FACTOR
		self._lists = []
		self._maxes = []
		self._index = []
		self._offset = 0
		if iterable is not None:
			self._update(iterable)

	def __new__(cls, iterable=None):
		return object.__new__(cls)

	def _reset(self, load):
		values = reduce(iadd, self._lists, [])
		self._clear()
		self._load = load
		self._update(values)

	def clear(self):
		self._len = 0
		del self._lists[:]
		del self._maxes[:]
		del self._index[:]
		self._offset = 0
	_clear = clear

	def add(self, value):
		_lists = self._lists
		_maxes = self._maxes
		if _maxes:
			pos = bisect_right(_maxes, value)
			if pos == len(_maxes):
				pos -= 1
				_lists[pos].append(value)
				_maxes[pos] = value
			else:
				insort(_lists[pos], value)
			self._expand(pos)
		else:
			_lists.append([value])
			_maxes.append(value)
		self._len += 1

	def _expand(self, pos):
		_load = self._load
		_lists = self._lists
		_index = self._index
		if len(_lists[pos]) > _load << 1:
			_maxes = self._maxes
			_lists_pos = _lists[pos]
			half = _lists_pos[_load:]
			del _lists_pos[_load:]
			_maxes[pos] = _lists_pos[-1]
			_lists.insert(pos + 1, half)
			_maxes.insert(pos + 1, half[-1])
			del _index[:]
		elif _index:
			child = self._offset + pos
			while child:
				_index[child] += 1
				child = child - 1 >> 1
			_index[0] += 1

	def update(self, iterable):
		_lists = self._lists
		_maxes = self._maxes
		values = sorted(iterable)
		if _maxes:
			if len(values) * 4 >= self._len:
				_lists.append(values)
				values = reduce(iadd, _lists, [])
				values.sort()
				self._clear()
			else:
				_add = self.add
				for val in values:
					_add(val)
				return
		_load = self._load
		_lists.extend((values[pos:pos + _load] for pos in range(0, len(values), _load)))
		_maxes.extend((sublist[-1] for sublist in _lists))
		self._len = len(values)
		del self._index[:]
	_update = update

	def __contains__(self, value):
		_maxes = self._maxes
		if not _maxes:
			return False
		pos = bisect_left(_maxes, value)
		if pos == len(_maxes):
			return False
		_lists = self._lists
		idx = bisect_left(_lists[pos], value)
		return _lists[pos][idx] == value

	def discard(self, value):
		_maxes = self._maxes
		if not _maxes:
			return
		pos = bisect_left(_maxes, value)
		if pos == len(_maxes):
			return
		_lists = self._lists
		idx = bisect_left(_lists[pos], value)
		if _lists[pos][idx] == value:
			self._delete(pos, idx)

	def remove(self, value):
		_maxes = self._maxes
		if not _maxes:
			raise ValueError('{0!r} not in list'.format(value))
		pos = bisect_left(_maxes, value)
		if pos == len(_maxes):
			raise ValueError('{0!r} not in list'.format(value))
		_lists = self._lists
		idx = bisect_left(_lists[pos], value)
		if _lists[pos][idx] == value:
			self._delete(pos, idx)
		else:
			raise ValueError('{0!r} not in list'.format(value))

	def _delete(self, pos, idx):
		_lists = self._lists
		_maxes = self._maxes
		_index = self._index
		_lists_pos = _lists[pos]
		del _lists_pos[idx]
		self._len -= 1
		len_lists_pos = len(_lists_pos)
		if len_lists_pos > self._load >> 1:
			_maxes[pos] = _lists_pos[-1]
			if _index:
				child = self._offset + pos
				while child > 0:
					_index[child] -= 1
					child = child - 1 >> 1
				_index[0] -= 1
		elif len(_lists) > 1:
			if not pos:
				pos += 1
			prev = pos - 1
			_lists[prev].extend(_lists[pos])
			_maxes[prev] = _lists[prev][-1]
			del _lists[pos]
			del _maxes[pos]
			del _index[:]
			self._expand(prev)
		elif len_lists_pos:
			_maxes[pos] = _lists_pos[-1]
		else:
			del _lists[pos]
			del _maxes[pos]
			del _index[:]

	def _loc(self, pos, idx):
		if not pos:
			return idx
		_index = self._index
		if not _index:
			self._build_index()
		total = 0
		pos += self._offset
		while pos:
			if not pos & 1:
				total += _index[pos - 1]
			pos = pos - 1 >> 1
		return total + idx

	def _pos(self, idx):
		if idx < 0:
			last_len = len(self._lists[-1])
			if -idx <= last_len:
				return (len(self._lists) - 1, last_len + idx)
			idx += self._len
			if idx < 0:
				raise IndexError('list index out of range')
		elif idx >= self._len:
			raise IndexError('list index out of range')
		if idx < len(self._lists[0]):
			return (0, idx)
		_index = self._index
		if not _index:
			self._build_index()
		pos = 0
		child = 1
		len_index = len(_index)
		while child < len_index:
			index_child = _index[child]
			if idx < index_child:
				pos = child
			else:
				idx -= index_child
				pos = child + 1
			child = (pos << 1) + 1
		return (pos - self._offset, idx)

	def _build_index(self):
		row0 = list(map(len, self._lists))
		if len(row0) == 1:
			self._index[:] = row0
			self._offset = 0
			return
		head = iter(row0)
		tail = iter(head)
		row1 = list(starmap(add, zip(head, tail)))
		if len(row0) & 1:
			row1.append(row0[-1])
		if len(row1) == 1:
			self._index[:] = row1 + row0
			self._offset = 1
			return
		size = 2 ** (int(log(len(row1) - 1, 2)) + 1)
		row1.extend(repeat(0, size - len(row1)))
		tree = [row0, row1]
		while len(tree[-1]) > 1:
			head = iter(tree[-1])
			tail = iter(head)
			row = list(starmap(add, zip(head, tail)))
			tree.append(row)
		reduce(iadd, reversed(tree), self._index)
		self._offset = size * 2 - 1

	def __delitem__(self, index):
		if isinstance(index, slice):
			(start, stop, step) = index.indices(self._len)
			if step == 1 and start < stop:
				if start == 0 and stop == self._len:
					return self._clear()
				elif self._len <= 8 * (stop - start):
					values = self._getitem(slice(None, start))
					if stop < self._len:
						values += self._getitem(slice(stop, None))
					self._clear()
					return self._update(values)
			indices = range(start, stop, step)
			if step > 0:
				indices = reversed(indices)
			(_pos, _delete) = (self._pos, self._delete)
			for index in indices:
				(pos, idx) = _pos(index)
				_delete(pos, idx)
		else:
			(pos, idx) = self._pos(index)
			self._delete(pos, idx)

	def __getitem__(self, index):
		_lists = self._lists
		if isinstance(index, slice):
			(start, stop, step) = index.indices(self._len)
			if step == 1 and start < stop:
				if start == 0 and stop == self._len:
					return reduce(iadd, self._lists, [])
				(start_pos, start_idx) = self._pos(start)
				start_list = _lists[start_pos]
				stop_idx = start_idx + stop - start
				if len(start_list) >= stop_idx:
					return start_list[start_idx:stop_idx]
				if stop == self._len:
					stop_pos = len(_lists) - 1
					stop_idx = len(_lists[stop_pos])
				else:
					(stop_pos, stop_idx) = self._pos(stop)
				prefix = _lists[start_pos][start_idx:]
				middle = _lists[start_pos + 1:stop_pos]
				result = reduce(iadd, middle, prefix)
				result += _lists[stop_pos][:stop_idx]
				return result
			if step == -1 and start > stop:
				result = self._getitem(slice(stop + 1, start + 1))
				result.reverse()
				return result
			indices = range(start, stop, step)
			return list((self._getitem(index) for index in indices))
		else:
			if self._len:
				if index == 0:
					return _lists[0][0]
				elif index == -1:
					return _lists[-1][-1]
			else:
				raise IndexError('list index out of range')
			if 0 <= index < len(_lists[0]):
				return _lists[0][index]
			len_last = len(_lists[-1])
			if -len_last < index < 0:
				return _lists[-1][len_last + index]
			(pos, idx) = self._pos(index)
			return _lists[pos][idx]
	_getitem = __getitem__

	def __setitem__(self, index, value):
		message = 'use ``del sl[index]`` and ``sl.add(value)`` instead'
		raise NotImplementedError(message)

	def __iter__(self):
		return chain.from_iterable(self._lists)

	def __reversed__(self):
		return chain.from_iterable(map(reversed, reversed(self._lists)))

	def reverse(self):
		raise NotImplementedError('use ``reversed(sl)`` instead')

	def islice(self, start=None, stop=None, reverse=False):
		_len = self._len
		if not _len:
			return iter(())
		(start, stop, _) = slice(start, stop).indices(self._len)
		if start >= stop:
			return iter(())
		_pos = self._pos
		(min_pos, min_idx) = _pos(start)
		if stop == _len:
			max_pos = len(self._lists) - 1
			max_idx = len(self._lists[-1])
		else:
			(max_pos, max_idx) = _pos(stop)
		return self._islice(min_pos, min_idx, max_pos, max_idx, reverse)

	def _islice(self, min_pos, min_idx, max_pos, max_idx, reverse):
		_lists = self._lists
		if min_pos > max_pos:
			return iter(())
		if min_pos == max_pos:
			if reverse:
				indices = reversed(range(min_idx, max_idx))
				return map(_lists[min_pos].__getitem__, indices)
			indices = range(min_idx, max_idx)
			return map(_lists[min_pos].__getitem__, indices)
		next_pos = min_pos + 1
		if next_pos == max_pos:
			if reverse:
				min_indices = range(min_idx, len(_lists[min_pos]))
				max_indices = range(max_idx)
				return chain(map(_lists[max_pos].__getitem__, reversed(max_indices)), map(_lists[min_pos].__getitem__, reversed(min_indices)))
			min_indices = range(min_idx, len(_lists[min_pos]))
			max_indices = range(max_idx)
			return chain(map(_lists[min_pos].__getitem__, min_indices), map(_lists[max_pos].__getitem__, max_indices))
		if reverse:
			min_indices = range(min_idx, len(_lists[min_pos]))
			sublist_indices = range(next_pos, max_pos)
			sublists = map(_lists.__getitem__, reversed(sublist_indices))
			max_indices = range(max_idx)
			return chain(map(_lists[max_pos].__getitem__, reversed(max_indices)), chain.from_iterable(map(reversed, sublists)), map(_lists[min_pos].__getitem__, reversed(min_indices)))
		min_indices = range(min_idx, len(_lists[min_pos]))
		sublist_indices = range(next_pos, max_pos)
		sublists = map(_lists.__getitem__, sublist_indices)
		max_indices = range(max_idx)
		return chain(map(_lists[min_pos].__getitem__, min_indices), chain.from_iterable(sublists), map(_lists[max_pos].__getitem__, max_indices))

	def irange(self, minimum=None, maximum=None, inclusive=(True, True), reverse=False):
		_maxes = self._maxes
		if not _maxes:
			return iter(())
		_lists = self._lists
		if minimum is None:
			min_pos = 0
			min_idx = 0
		elif inclusive[0]:
			min_pos = bisect_left(_maxes, minimum)
			if min_pos == len(_maxes):
				return iter(())
			min_idx = bisect_left(_lists[min_pos], minimum)
		else:
			min_pos = bisect_right(_maxes, minimum)
			if min_pos == len(_maxes):
				return iter(())
			min_idx = bisect_right(_lists[min_pos], minimum)
		if maximum is None:
			max_pos = len(_maxes) - 1
			max_idx = len(_lists[max_pos])
		elif inclusive[1]:
			max_pos = bisect_right(_maxes, maximum)
			if max_pos == len(_maxes):
				max_pos -= 1
				max_idx = len(_lists[max_pos])
			else:
				max_idx = bisect_right(_lists[max_pos], maximum)
		else:
			max_pos = bisect_left(_maxes, maximum)
			if max_pos == len(_maxes):
				max_pos -= 1
				max_idx = len(_lists[max_pos])
			else:
				max_idx = bisect_left(_lists[max_pos], maximum)
		return self._islice(min_pos, min_idx, max_pos, max_idx, reverse)

	def __len__(self):
		return self._len

	def bisect_left(self, value):
		_maxes = self._maxes
		if not _maxes:
			return 0
		pos = bisect_left(_maxes, value)
		if pos == len(_maxes):
			return self._len
		idx = bisect_left(self._lists[pos], value)
		return self._loc(pos, idx)

	def bisect_right(self, value):
		_maxes = self._maxes
		if not _maxes:
			return 0
		pos = bisect_right(_maxes, value)
		if pos == len(_maxes):
			return self._len
		idx = bisect_right(self._lists[pos], value)
		return self._loc(pos, idx)
	bisect = bisect_right
	_bisect_right = bisect_right

	def count(self, value):
		_maxes = self._maxes
		if not _maxes:
			return 0
		pos_left = bisect_left(_maxes, value)
		if pos_left == len(_maxes):
			return 0
		_lists = self._lists
		idx_left = bisect_left(_lists[pos_left], value)
		pos_right = bisect_right(_maxes, value)
		if pos_right == len(_maxes):
			return self._len - self._loc(pos_left, idx_left)
		idx_right = bisect_right(_lists[pos_right], value)
		if pos_left == pos_right:
			return idx_right - idx_left
		right = self._loc(pos_right, idx_right)
		left = self._loc(pos_left, idx_left)
		return right - left

	def copy(self):
		return self.__class__(self)
	__copy__ = copy

	def append(self, value):
		raise NotImplementedError('use ``sl.add(value)`` instead')

	def extend(self, values):
		raise NotImplementedError('use ``sl.update(values)`` instead')

	def insert(self, index, value):
		raise NotImplementedError('use ``sl.add(value)`` instead')

	def pop(self, index=-1):
		if not self._len:
			raise IndexError('pop index out of range')
		_lists = self._lists
		if index == 0:
			val = _lists[0][0]
			self._delete(0, 0)
			return val
		if index == -1:
			pos = len(_lists) - 1
			loc = len(_lists[pos]) - 1
			val = _lists[pos][loc]
			self._delete(pos, loc)
			return val
		if 0 <= index < len(_lists[0]):
			val = _lists[0][index]
			self._delete(0, index)
			return val
		len_last = len(_lists[-1])
		if -len_last < index < 0:
			pos = len(_lists) - 1
			loc = len_last + index
			val = _lists[pos][loc]
			self._delete(pos, loc)
			return val
		(pos, idx) = self._pos(index)
		val = _lists[pos][idx]
		self._delete(pos, idx)
		return val

	def index(self, value, start=None, stop=None):
		_len = self._len
		if not _len:
			raise ValueError('{0!r} is not in list'.format(value))
		if start is None:
			start = 0
		if start < 0:
			start += _len
		if start < 0:
			start = 0
		if stop is None:
			stop = _len
		if stop < 0:
			stop += _len
		if stop > _len:
			stop = _len
		if stop <= start:
			raise ValueError('{0!r} is not in list'.format(value))
		_maxes = self._maxes
		pos_left = bisect_left(_maxes, value)
		if pos_left == len(_maxes):
			raise ValueError('{0!r} is not in list'.format(value))
		_lists = self._lists
		idx_left = bisect_left(_lists[pos_left], value)
		if _lists[pos_left][idx_left] != value:
			raise ValueError('{0!r} is not in list'.format(value))
		stop -= 1
		left = self._loc(pos_left, idx_left)
		if start <= left:
			if left <= stop:
				return left
		else:
			right = self._bisect_right(value) - 1
			if start <= right:
				return start
		raise ValueError('{0!r} is not in list'.format(value))

	def __add__(self, other):
		values = reduce(iadd, self._lists, [])
		values.extend(other)
		return self.__class__(values)
	__radd__ = __add__

	def __iadd__(self, other):
		self._update(other)
		return self

	def __mul__(self, num):
		values = reduce(iadd, self._lists, []) * num
		return self.__class__(values)
	__rmul__ = __mul__

	def __imul__(self, num):
		values = reduce(iadd, self._lists, []) * num
		self._clear()
		self._update(values)
		return self

	def __make_cmp(seq_op, symbol, doc):

		def comparer(self, other):
			if not isinstance(other, Sequence):
				return NotImplemented
			self_len = self._len
			len_other = len(other)
			if self_len != len_other:
				if seq_op is eq:
					return False
				if seq_op is ne:
					return True
			for (alpha, beta) in zip(self, other):
				if alpha != beta:
					return seq_op(alpha, beta)
			return seq_op(self_len, len_other)
		seq_op_name = seq_op.__name__
		comparer.__name__ = '__{0}__'.format(seq_op_name)
		return comparer
	__eq__ = __make_cmp(eq, '==', 'equal to')
	__ne__ = __make_cmp(ne, '!=', 'not equal to')
	__lt__ = __make_cmp(lt, '<', 'less than')
	__gt__ = __make_cmp(gt, '>', 'greater than')
	__le__ = __make_cmp(le, '<=', 'less than or equal to')
	__ge__ = __make_cmp(ge, '>=', 'greater than or equal to')
	__make_cmp = staticmethod(__make_cmp)

	def __reduce__(self):
		values = reduce(iadd, self._lists, [])
		return (type(self), (values,))

	@recursive_repr()
	def __repr__(self):
		return '{0}({1!r})'.format(type(self).__name__, list(self))

	def _check(self):
		try:
			assert self._load >= 4
			assert len(self._maxes) == len(self._lists)
			assert self._len == sum((len(sublist) for sublist in self._lists))
			for sublist in self._lists:
				for pos in range(1, len(sublist)):
					assert sublist[pos - 1] <= sublist[pos]
			for pos in range(1, len(self._lists)):
				assert self._lists[pos - 1][-1] <= self._lists[pos][0]
			for pos in range(len(self._maxes)):
				assert self._maxes[pos] == self._lists[pos][-1]
			double = self._load << 1
			assert all((len(sublist) <= double for sublist in self._lists))
			half = self._load >> 1
			for pos in range(0, len(self._lists) - 1):
				assert len(self._lists[pos]) >= half
			if self._index:
				assert self._len == self._index[0]
				assert len(self._index) == self._offset + len(self._lists)
				for pos in range(len(self._lists)):
					leaf = self._index[self._offset + pos]
					assert leaf == len(self._lists[pos])
				for pos in range(self._offset):
					child = (pos << 1) + 1
					if child >= len(self._index):
						assert self._index[pos] == 0
					elif child + 1 == len(self._index):
						assert self._index[pos] == self._index[child]
					else:
						child_sum = self._index[child] + self._index[child + 1]
						assert child_sum == self._index[pos]
		except:
			traceback.print_exc(file=sys.stdout)
			print('len', self._len)
			print('load', self._load)
			print('offset', self._offset)
			print('len_index', len(self._index))
			print('index', self._index)
			print('len_maxes', len(self._maxes))
			print('maxes', self._maxes)
			print('len_lists', len(self._lists))
			print('lists', self._lists)
			raise
output = []
for _t in range(int(input())):
	n = int(input())
	p = list(map(int, input().split()))
	ans = 0
	sl = SortedList()
	for (i, num) in enumerate(p):
		first_at_least = bisect_left(sl, num)
		first_bigger = bisect_right(sl, num, first_at_least)
		ans += min(first_at_least, i - first_bigger)
		sl.add(num)
	output.append(ans)
sys.stdout.write('\n'.join(map(str, output)))


import sys
import getpass
from collections import Counter, defaultdict
input = sys.stdin.readline
M9 = 10 ** 9 + 7
(yes, no) = ('YES', 'NO')
MAXINT = sys.maxsize
OFFLINE_TEST = getpass.getuser() == 'hkmac'

def log(*args):
	if OFFLINE_TEST:
		print('\x1b[36m', *args, '\x1b[0m', file=sys.stderr)

def solve(*args):
	if OFFLINE_TEST:
		log('----- solving ------')
		log(*args)
		log('----- ------- ------')
	return solve_(*args)

def read_matrix(rows):
	return [list(map(int, input().split())) for _ in range(rows)]

def read_strings(rows):
	return [input().strip() for _ in range(rows)]

def minus_one(arr):
	return [x - 1 for x in arr]

def minus_one_matrix(mrr):
	return [[x - 1 for x in row] for row in mrr]

class FenwickTree:

	def __init__(self, bits=17):
		self.LARGE = 2 ** bits
		self.c = [0] * (self.LARGE + 10)

	def update(self, x, increment):
		x += 1
		while x <= self.LARGE:
			self.c[x] += increment
			x += x & -x

	def query(self, x):
		x += 1
		res = 0
		while x > 0:
			res += self.c[x]
			x -= x & -x
		return res

def solve_():
	arr = list(map(int, input().split()))
	cmp = {a: i + 2 for (i, a) in enumerate(sorted(set(arr)))}
	arr = [cmp[a] for a in arr]
	c = Counter()
	f = FenwickTree(bits=len(bin(max(arr))))
	c[arr[0]] += 1
	f.update(arr[0], 1)
	res = 0
	for (i, x) in enumerate(arr[1:], start=1):
		val = f.query(x - 1)
		res += min(val, i - c[x] - val)
		f.update(x, 1)
		c[x] += 1
	return res
for case_num in range(int(input())):
	k = int(input())
	res = solve()
	print(res)


import os
import sys
import math
import collections
import functools
import itertools
import heapq
import bisect
from io import BytesIO, IOBase

def vsInput():
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
ALPHA = 'abcde'
MOD = 10 ** 9 + 7
EPS = 1e-06
INF = 10 ** 18

def Ceil(a, b):
	return a // b + int(a % b > 0)

def INT():
	return int(input())

def STR():
	return input()

def INTS():
	return tuple(map(int, input().split()))

def ARRINT():
	return [int(i) for i in input().split()]

def ARRSTR():
	return [i for i in input().split()]

class BIT:

	def __init__(self, n):
		self.n = n
		self.a = [0] * (n + 1)

	def update(self, x, v):
		while x <= self.n:
			self.a[x] += v
			x += x & -x

	def query(self, x):
		res = 0
		while x:
			res += self.a[x]
			x -= x & -x
		return res

def solve(n, a):
	b = sorted(a)
	for i in range(n):
		a[i] = bisect.bisect_left(b, a[i]) + 1
	bit = BIT(n)
	res = 0
	for i in range(n):
		l = bit.query(a[i] - 1)
		r = bit.query(a[i])
		res += min(l, i - r)
		bit.update(a[i], 1)
	print(res)
for t in range(INT()):
	n = INT()
	a = ARRINT()
	solve(n, a)


import sys
input = sys.stdin.buffer.readline

def queries(l, r):
	count = 0
	while l <= r:
		if l % 2 == 1:
			count += sgn_tree[l]
			l += 1
		if r % 2 == 0:
			count += sgn_tree[r]
			r -= 1
		l = l >> 1
		r = r >> 1
	return count

def update(indx):
	sgn_tree[indx] += 1
	new_indx = indx >> 1
	while new_indx >= 1:
		sgn_tree[new_indx] = sgn_tree[2 * new_indx] + sgn_tree[2 * new_indx + 1]
		new_indx = new_indx >> 1
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	brr = arr[:]
	arr.sort()
	count = 0
	d = {}
	for i in range(n):
		if arr[i] not in d:
			d[arr[i]] = count
			count += 1
	sgn_tree = [0 for i in range(2 * n)]
	ans = 0
	for i in range(n):
		left_tree = queries(n, d[brr[i]] + n - 1)
		right_tree = queries(d[brr[i]] + 1 + n, 2 * n - 1)
		if left_tree <= right_tree:
			ans += left_tree
		else:
			ans += right_tree
		update(d[brr[i]] + n)
	print(ans)


import sys
input = sys.stdin.readline
from collections import defaultdict

class Fenwick:

	def __init__(self, n):
		self.a = [0] * (n + 1)

	def sum(self, i):
		s = 0
		while i > 0:
			s += self.a[i]
			i -= i & -i
		return s

	def add(self, i, x):
		while i < len(self.a):
			self.a[i] += x
			i += i & -i

def solve(A, n):
	count = defaultdict(int)
	B = sorted(set(A))
	m = {c: i for (i, c) in enumerate(B, 1)}
	fen = Fenwick(len(B))
	ans = 0
	total = 0
	for a in A:
		i = m[a]
		smaller = fen.sum(i - 1)
		larger = total - smaller - count[a]
		ans += min(smaller, larger)
		fen.add(i, 1)
		total += 1
		count[a] += 1
	return ans
T = int(input())
for _ in range(T):
	n = int(input())
	A = list(map(int, input().split()))
	print(solve(A, n))


import bisect

def update(BIT, index, val):
	while index < len(BIT):
		BIT[index] += val
		index += index & -index

def sumQuery(BIT, index):
	total = 0
	while index > 0:
		total += BIT[index]
		index -= index & -index
	return total

def rangeQuery(BIT, l, r):
	return sumQuery(BIT, r) - sumQuery(BIT, l - 1)

def solve(queue, n, ans):
	copy = list(set(queue[:]))
	copy.sort()
	BIT = [0] * (len(copy) + 1)
	total = 0
	for i in queue:
		index = bisect.bisect(copy, i - 1) + 1
		total += min(rangeQuery(BIT, 1, index - 1), rangeQuery(BIT, index + 1, len(copy)))
		update(BIT, index, 1)
	ans.append(str(total))

def main():
	t = int(input())
	ans = []
	for i in range(t):
		n = int(input())
		arr = list(map(int, input().split()))
		solve(arr, n, ans)
	print('\n'.join(ans))
main()


from sys import stdin, stdout

def update_bit(i, bit_a, v):
	while i < len(bit_a):
		bit_a[i] += v
		i += i & -i

def query_bit(i, bit_a):
	r = 0
	while i > 0:
		r += bit_a[i]
		i -= i & -i
	return r

def solve(n, a_a):
	sa_a = list(set(a_a))
	sa_a.sort()
	dic = {}
	for i in range(1, len(sa_a) + 1):
		dic[sa_a[i - 1]] = i
	res = 0
	ttl = 0
	bit_a = [0] * (len(sa_a) + 1)
	for a in a_a:
		idx = dic[a]
		res += min(query_bit(idx - 1, bit_a), ttl - query_bit(idx, bit_a))
		ttl += 1
		update_bit(idx, bit_a, 1)
	return res
t = int(stdin.readline())
for _ in range(t):
	n = int(stdin.readline())
	a_a = list(map(int, stdin.readline().split()))
	res = solve(n, a_a)
	stdout.write(str(res) + '\n')


import sys
import bisect
from bisect import bisect_left as lb
from bisect import bisect_right as rb
input_ = lambda : sys.stdin.readline().strip('\r\n')
from math import log
from math import gcd
from math import atan2, acos
from random import randint
sa = lambda : input_()
sb = lambda : int(input_())
sc = lambda : input_().split()
sd = lambda : list(map(int, input_().split()))
sflo = lambda : list(map(float, input_().split()))
se = lambda : float(input_())
sf = lambda : list(input_())
flsh = lambda : sys.stdout.flush()
mod = 10 ** 9 + 7
mod1 = 998244353
gp = []
cost = []
dp = []
mx = []
ans1 = []
ans2 = []
special = []
specnode = []
a = 0
kthpar = []

def dfs2(root, par):
	if par != -1:
		dp[root] = dp[par] + 1
	for i in range(1, 20):
		if kthpar[root][i - 1] != -1:
			kthpar[root][i] = kthpar[kthpar[root][i - 1]][i - 1]
	for child in gp[root]:
		if child == par:
			continue
		kthpar[child][0] = root
		dfs(child, root)
ans = 0
b = []
vis = []
tot = 0
time = []
time1 = []
adj = []
mx = -1
eps = 1e-07

def update_it(bit, i, val):
	n = len(bit)
	while i < n:
		bit[i] += val
		i += i & -i

def get_ans(bit, i):
	n = len(bit)
	tot = 0
	while i > 0:
		tot += bit[i]
		i -= i & -i
	return tot

def hnbhai(tc):
	n = sb()
	a = sd()
	s = []
	for i in a:
		s.append(i)
	s.sort()
	d = {}
	for i in s:
		d[i] = []
	for i in range(len(s)):
		d[s[i]].append(i + 1)
	for i in range(n):
		a[i] = d[a[i]][0]
	bit = [0] * (len(a) + 2)
	tot = 0
	for i in range(n):
		tot += min(get_ans(bit, a[i] - 1), i - get_ans(bit, a[i]))
		update_it(bit, a[i], 1)
	print(tot)
for _ in range(sb()):
	hnbhai(_ + 1)


import math
from heapq import heappush, heappop, heapify
import random
import string
from collections import deque, defaultdict
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())
mod1 = 1000000000 + 7
mod2 = 998244353
for _ in range(I()):
	n = I()
	a = L()
	b = sorted(a)
	order = {}
	uindex = 1
	for i in b:
		if i not in order:
			order[i] = uindex
			uindex += 1
	for i in range(n):
		a[i] = order[a[i]]
	fentree = [0] * (n + 1)

	def smallcount(x):
		res = 0
		while x > 0:
			res += fentree[x]
			x -= x & -x
		return res

	def update(x):
		while x <= n:
			fentree[x] += 1
			x += x & -x
	ans = 0
	covered = [0] * (n + 1)
	for i in range(n):
		s = smallcount(a[i])
		ans += min(s - covered[a[i]], i - s)
		covered[a[i]] += 1
		update(a[i])
	print(ans)


class BIT:

	def __init__(self, n):
		self.n = n
		self.bit = [0] * (self.n + 1)

	def init(self, init_val):
		for (i, v) in enumerate(init_val):
			self.add(i, v)

	def add(self, i, x):
		i += 1
		while i <= self.n:
			self.bit[i] += x
			i += i & -i

	def sum(self, i, j):
		return self._sum(j) - self._sum(i)

	def _sum(self, i):
		res = 0
		while i > 0:
			res += self.bit[i]
			i -= i & -i
		return res

	def lower_bound(self, x):
		s = 0
		pos = 0
		depth = self.n.bit_length()
		v = 1 << depth
		for i in range(depth, -1, -1):
			k = pos + v
			if k <= self.n and s + self.bit[k] < x:
				s += self.bit[k]
				pos += v
			v >>= 1
		return pos

	def __str__(self):
		arr = [self.sum(i, i + 1) for i in range(self.n)]
		return str(arr)
import sys
import io, os
input = sys.stdin.buffer.readline
t = int(input())
from collections import deque
for _ in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	X = set(A)
	X = list(X)
	X.sort()
	toid = {}
	for (i, x) in enumerate(X):
		toid[x] = i
	A = [toid[a] for a in A]
	bit = BIT(n + 2)
	q = deque([])
	ans = 0
	for p in A:
		m = bit.sum(0, p)
		M = bit.sum(p + 1, bit.n)
		if m < M:
			ans += m
		else:
			ans += M
		bit.add(p, 1)
	print(ans)


import sys
readline = sys.stdin.readline

class FenwickTree:

	def __init__(self, n):
		self.size = n
		self.tree = [0] * (n + 1)

	def sum(self, i):
		out = 0
		while i > 0:
			out += self.tree[i]
			i -= i & -i
		return out

	def add(self, i, x):
		while i <= self.size:
			self.tree[i] += x
			i += i & -i
T = int(readline())
for t in range(T):
	N = int(readline())
	A = list(map(int, readline().split()))
	za = sorted(list(set(A)))
	n = len(za)
	dic = {}
	for (i, z) in enumerate(za):
		dic[z] = i
	for i in range(len(A)):
		A[i] = dic[A[i]] + 1
	BIT = FenwickTree(n + 1)
	ans = 0
	for a in A:
		small = BIT.sum(a - 1)
		large = BIT.sum(n + 1) - BIT.sum(a)
		if small < large:
			ans += small
		else:
			ans += large
		BIT.add(a, 1)
	print(ans)


import bisect

def solve():
	n = int(input())
	p = [int(v) for v in input().split()]
	arr = sorted(set(p))
	tree = [0] * n
	ans = 0

	def inc(i):
		while i < n:
			tree[i] += 1
			i |= i + 1

	def part_sum(i):
		ans = 0
		while i >= 0:
			ans += tree[i]
			i = (i & i + 1) - 1
		return ans

	def sum(l, r):
		if l == 0:
			return part_sum(r)
		else:
			return part_sum(r) - part_sum(l - 1)
	inc(bisect.bisect_left(arr, p[0]))
	for i in range(1, n):
		pos = bisect.bisect_left(arr, p[i])
		l = sum(0, pos - 1) if pos else 0
		r = sum(pos + 1, n - 1) if pos + 1 < n else 0
		ans += min(l, r)
		inc(pos)
	print(ans)
for _ in range(int(input())):
	solve()


import os, sys
from io import BytesIO, IOBase
from math import log2, ceil, sqrt, gcd
from _collections import deque
import heapq as hp
from bisect import bisect_left, bisect_right
from math import cos, sin
from itertools import permutations
from operator import itemgetter
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
mod = 10 ** 9 + 7

def update(i, vl):
	i += n + 1
	tree[i] += vl
	while i:
		tree[i >> 1] = tree[i] + tree[i ^ 1]
		i >>= 1

def query(l, r):
	l += n + 1
	r += n + 1
	ans = 0
	while l < r:
		if l & 1:
			ans += tree[l]
			l += 1
		if r & 1:
			r -= 1
			ans += tree[r]
		l >>= 1
		r >>= 1
	return ans
for _ in range(int(input())):
	n = int(input())
	tree = [0] * (2 * n + 5)
	a = list(map(int, input().split()))
	s = set()
	for i in a:
		s.add(i)
	d = dict()
	id = 1
	for i in sorted(s):
		d[i] = id
		id += 1
	for i in range(n):
		a[i] = d[a[i]]
	ans = 0
	for i in a:
		x = query(0, i)
		y = query(i + 1, id + 1)
		ans += min(x, y)
		update(i, 1)
	print(ans)


import io, os
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

class fenwick(object):

	def __init__(self, n):
		self.n = n
		self.cul = [0] * n

	def update(self, index, diff):
		i = index
		while i < self.n:
			self.cul[i] += diff
			i += i + 1 & -i - 1

	def getaccu(self, index):
		output = 0
		i = index
		while i >= 0:
			output += self.cul[i]
			i -= i + 1 & -i - 1
		return output

def main(t):
	n = int(input())
	arr = list(map(int, input().split()))
	sortedarr = sorted(arr)
	dic = {}
	fre = []
	index = 0
	for num in sortedarr:
		if num not in dic:
			dic[num] = index
			index += 1
	fre = fenwick(index)
	occupy = {}
	ans = 0
	for (i, num) in enumerate(arr):
		if num not in occupy:
			occupy[num] = 0
		occupy[num] += 1
		curr = dic[num]
		fre.update(curr, 1)
		front = fre.getaccu(curr - 1)
		rear = i + 1 - front - occupy[num]
		ans += min(front, rear)
	print(ans)
T = int(input())
t = 1
while t <= T:
	main(t)
	t += 1


import sys
from sys import stdin
from collections import deque

def bitadd(a, w, bit):
	x = a
	while x <= len(bit) - 1:
		bit[x] += w
		x += x & -1 * x

def bitsum(a, bit):
	if a <= 0:
		return 0
	ret = 0
	x = a
	while x > 0:
		ret += bit[x]
		x -= x & -1 * x
	return ret
tt = int(stdin.readline())
ANS = []
for loop in range(tt):
	n = int(stdin.readline())
	a = list(map(int, stdin.readline().split()))
	dic = {}
	lis = []
	for i in a:
		if i not in dic:
			dic[i] = 0
			lis.append(i)
	lis.sort()
	for i in range(len(lis)):
		dic[lis[i]] = i + 1
	BIT = [0] * (len(lis) + 1)
	ans = 0
	for i in range(n):
		ni = dic[a[i]]
		mini = bitsum(ni - 1, BIT)
		eq = bitsum(ni, BIT)
		maxi = i - eq
		ans += min(maxi, mini)
		bitadd(ni, 1, BIT)
	ANS.append(str(ans))
print('\n'.join(ANS))


from sys import stdin, stdout
from math import gcd, sqrt, factorial, pi, inf
from collections import deque, defaultdict
from bisect import bisect, bisect_left
from time import time
from itertools import permutations as per
from heapq import heapify, heappush, heappop, heappushpop
input = stdin.readline
R = lambda : map(int, input().split())
I = lambda : int(input())
S = lambda : input().rstrip('\r\n')
L = lambda : list(R())
P = lambda x: stdout.write(str(x) + '\n')
lcm = lambda x, y: x * y // gcd(x, y)
nCr = lambda x, y: f[x] * inv(f[y] * f[x - y] % N) % N
inv = lambda x: pow(x, N - 2, N)
sm = lambda x: (x ** 2 + x) // 2
N = 10 ** 9 + 7

def tr_len(n):
	p = 1
	while p < n:
		p <<= 1
	return p + p - 1

def get_val(l, h, st, ed, p):
	if l > ed or h < st:
		return 0
	elif l >= st and h <= ed:
		return tr[p]
	else:
		mid = (l + h) // 2
		return get_val(l, mid, st, ed, 2 * p + 1) + get_val(mid + 1, h, st, ed, 2 * p + 2)

def update(l, h, p, ind, val):
	if l == h == ind:
		tr[p] += 1
	elif l <= ind <= h:
		tr[p] += 1
		mid = (l + h) // 2
		update(l, mid, 2 * p + 1, ind, val)
		update(mid + 1, h, 2 * p + 2, ind, val)
for _ in range(I()):
	n = I()
	a = L()
	s = sorted(set(a))
	p = len(s)
	ind = {s[i]: i for i in range(p)}
	cnt = {i: 0 for i in s}
	ln = tr_len(p)
	tr = [0] * ln
	ans = 0
	l = 0
	r = p - 1
	c = 0
	for i in a:
		mn = 0 if ind[i] == l else get_val(l, ln // 2, l, ind[i] - 1, 0)
		ans += min(mn, c - (cnt[i] + mn))
		update(l, ln // 2, 0, ind[i], i)
		cnt[i] += 1
		c += 1
	print(ans)


import sys
input = sys.stdin.readline
t = int(input())
for tests in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	compression_dict = {a: ind + 2 for (ind, a) in enumerate(sorted(set(A)))}
	A = [compression_dict[a] for a in A]
	LEN = len(A) + 10
	BIT = [0] * (LEN + 1)

	def update(v, w):
		while v <= LEN:
			BIT[v] += w
			v += v & -v

	def getvalue(v):
		ANS = 0
		while v != 0:
			ANS += BIT[v]
			v -= v & -v
		return ANS
	ALL = 0
	ANS = 0
	for a in A:
		x = getvalue(a - 1)
		y = getvalue(a)
		z = ALL - y
		ANS += min(x, z)
		update(a, 1)
		ALL += 1
	print(ANS)


import sys
from io import BytesIO, IOBase
import os
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self, **kwargs):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

def inp():
	return sys.stdin.readline().strip()

def map_inp(v_type):
	return map(v_type, inp().split())

def list_inp(v_type):
	return list(map_inp(v_type))

def update(fen_tree, index):
	while index < len(fen_tree):
		fen_tree[index] += 1
		index += index & -index

def query(fen_tree, index):
	s = 0
	while index > 0:
		s += fen_tree[index]
		index -= index & -index
	return s
for _ in range(int(inp())):
	n = int(inp())
	arr = list_inp(int)
	dic = {}
	temp = list(set(arr))
	temp.sort()
	for i in range(len(temp)):
		dic[temp[i]] = i
	tree = [0 for item in range(len(temp) + 1)]
	ans = float('inf')
	answer = 0
	for item in arr:
		if ans == float('inf'):
			update(tree, dic[item] + 1)
			ans = item
			continue
		x = query(tree, len(temp)) - query(tree, dic[item] + 1)
		y = query(tree, dic[item])
		update(tree, dic[item] + 1)
		if x <= y:
			answer += x
		else:
			answer += y
			ans = item
	print(answer)


from collections import deque
import math

def buildSegmentTree(start, end, curr, seg, arr):
	if start == end:
		seg[curr] = [arr[start]]
		return
	mid = (start + end) // 2
	buildSegmentTree(start, mid, 2 * curr + 1, seg, arr)
	buildSegmentTree(mid + 1, end, 2 * curr + 2, seg, arr)
	seg[curr] = merge(seg[(curr << 1) + 1], seg[(curr << 1) + 2])

def merge(arr1, arr2):
	arr = []
	(i, j) = (0, 0)
	while i < len(arr1) and j < len(arr2):
		if arr1[i] < arr2[j]:
			arr.append(arr1[i])
			i += 1
		else:
			arr.append(arr2[j])
			j += 1
	while i < len(arr1):
		arr.append(arr1[i])
		i += 1
	while j < len(arr2):
		arr.append(arr2[j])
		j += 1
	return arr

def smaller(arr, ele, n):
	(l, h) = (0, n - 1)
	while l <= h:
		mid = (l + h) // 2
		if arr[mid] < ele:
			if mid + 1 < n and arr[mid + 1] < ele:
				l = mid + 1
			else:
				return mid + 1
		else:
			h = mid - 1
	return 0

def greater(arr, ele, n):
	(l, h) = (0, n - 1)
	while l <= h:
		mid = (l + h) // 2
		if arr[mid] > ele:
			if mid - 1 >= 0 and arr[mid - 1] > ele:
				h = mid - 1
			else:
				return n - mid
		else:
			l = mid + 1
	return 0

def queryS(l, r, ele, arrL, arrR, seg, idx):
	if arrL > r or arrR < l:
		return 0
	if arrL >= l and arrR <= r:
		return smaller(seg[idx], ele, arrR - arrL + 1)
	mid = (arrL + arrR) // 2
	return queryS(l, r, ele, arrL, mid, seg, 2 * idx + 1) + queryS(l, r, ele, mid + 1, arrR, seg, 2 * idx + 2)

def queryG(l, r, ele, arrL, arrR, seg, idx):
	if arrL > r or arrR < l:
		return 0
	if arrL >= l and arrR <= r:
		return greater(seg[idx], ele, arrR - arrL + 1)
	mid = (arrL + arrR) // 2
	return queryG(l, r, ele, arrL, mid, seg, 2 * idx + 1) + queryG(l, r, ele, mid + 1, arrR, seg, 2 * idx + 2)
t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split(' ')))
	ans = deque([arr[0]])
	h = math.floor(math.log2(n)) + 1
	seg = [0] * (1 << h + 1)
	buildSegmentTree(0, n - 1, 0, seg, arr)
	inv = 0
	(max_, min_) = (ans[0], ans[0])
	d = {arr[i]: 0 for i in range(n)}
	d[arr[0]] = 1
	for i in range(1, n):
		if arr[i] < min_:
			min_ = arr[i]
		elif arr[i] >= max_:
			max_ = arr[i]
		else:
			(g, s) = (0, 0)
			s = queryS(0, i - 1, arr[i], 0, n - 1, seg, 0)
			g = i - s - d[arr[i]]
			if g >= s:
				inv += s
			else:
				inv += g
		d[arr[i]] += 1
	print(inv)


from sys import stdin
input = stdin.readline

class segtree:

	def __init__(self, n):
		self.st = [0] * (4 * n)
		self.size = n - 1

	def update(self, ind, value):
		(l, h) = (0, self.size)
		i = 0
		while l < h:
			mid = (l + h) // 2
			if ind > mid:
				l = mid + 1
				i = 2 * i + 2
			else:
				i = 2 * i + 1
				h = mid
		self.st[i] += value
		while i > 0:
			i = (i - 1) // 2
			self.st[i] = self.st[2 * i + 1] + self.st[2 * i + 2]

	def query(self, x, y, l=0, h=-1, i=0):
		if h == -1:
			h = self.size
		if l >= x and h <= y:
			return self.st[i]
		if l > y or h < x:
			return 0
		mid = (l + h) // 2
		left = self.query(x, y, l, mid, 2 * i + 1)
		right = self.query(x, y, mid + 1, h, 2 * i + 2)
		return left + right

def answer():
	x = [[a[i], i] for i in range(n)]
	x.sort()
	st = segtree(n)
	(ans, prev) = (0, 10000000000.0)
	for i in range(n):
		if prev == x[i][0]:
			same += 1
		else:
			prev = x[i][0]
			same = 0
		less = st.query(0, x[i][1]) - same
		greater = x[i][1] - less - same
		ans += min(less, greater)
		st.update(x[i][1], 1)
	return ans
for T in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(answer())


import math
import random
import heapq, bisect
import sys
from collections import deque, defaultdict
from fractions import Fraction
import sys
from collections import defaultdict
mod = 10 ** 9 + 7
mod1 = 998244353
import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')

class TreeNode:

	def __init__(self, k, v):
		self.key = k
		self.value = v
		self.left = None
		self.right = None
		self.parent = None
		self.height = 1
		self.num_left = 1
		self.num_total = 1

class AvlTree:

	def __init__(self):
		self._tree = None

	def add(self, k, v):
		if not self._tree:
			self._tree = TreeNode(k, v)
			return
		node = self._add(k, v)
		if node:
			self._rebalance(node)

	def _add(self, k, v):
		node = self._tree
		while node:
			if k < node.key:
				if node.left:
					node = node.left
				else:
					node.left = TreeNode(k, v)
					node.left.parent = node
					return node.left
			elif node.key < k:
				if node.right:
					node = node.right
				else:
					node.right = TreeNode(k, v)
					node.right.parent = node
					return node.right
			else:
				node.value = v
				return

	@staticmethod
	def get_height(x):
		return x.height if x else 0

	@staticmethod
	def get_num_total(x):
		return x.num_total if x else 0

	def _rebalance(self, node):
		n = node
		while n:
			lh = self.get_height(n.left)
			rh = self.get_height(n.right)
			n.height = max(lh, rh) + 1
			balance_factor = lh - rh
			n.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)
			n.num_left = 1 + self.get_num_total(n.left)
			if balance_factor > 1:
				if self.get_height(n.left.left) < self.get_height(n.left.right):
					self._rotate_left(n.left)
				self._rotate_right(n)
			elif balance_factor < -1:
				if self.get_height(n.right.right) < self.get_height(n.right.left):
					self._rotate_right(n.right)
				self._rotate_left(n)
			else:
				n = n.parent

	def _remove_one(self, node):
		replacement = node.left or node.right
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = replacement
			else:
				node.parent.right = replacement
			replacement.parent = node.parent
			node.parent = None
		else:
			self._tree = replacement
			replacement.parent = None
		node.left = None
		node.right = None
		node.parent = None
		self._rebalance(replacement)

	def _remove_leaf(self, node):
		if node.parent:
			if AvlTree._is_left(node):
				node.parent.left = None
			else:
				node.parent.right = None
			self._rebalance(node.parent)
		else:
			self._tree = None
		node.parent = None
		node.left = None
		node.right = None

	def remove(self, k):
		node = self._get_node(k)
		if not node:
			return
		if AvlTree._is_leaf(node):
			self._remove_leaf(node)
			return
		if node.left and node.right:
			nxt = AvlTree._get_next(node)
			node.key = nxt.key
			node.value = nxt.value
			if self._is_leaf(nxt):
				self._remove_leaf(nxt)
			else:
				self._remove_one(nxt)
			self._rebalance(node)
		else:
			self._remove_one(node)

	def get(self, k):
		node = self._get_node(k)
		return node.value if node else -1

	def _get_node(self, k):
		if not self._tree:
			return None
		node = self._tree
		while node:
			if k < node.key:
				node = node.left
			elif node.key < k:
				node = node.right
			else:
				return node
		return None

	def get_at(self, pos):
		x = pos + 1
		node = self._tree
		while node:
			if x < node.num_left:
				node = node.left
			elif node.num_left < x:
				x -= node.num_left
				node = node.right
			else:
				return (node.key, node.value)
		raise IndexError('Out of ranges')

	@staticmethod
	def _is_left(node):
		return node.parent.left and node.parent.left == node

	@staticmethod
	def _is_leaf(node):
		return node.left is None and node.right is None

	def _rotate_right(self, node):
		if not node.parent:
			self._tree = node.left
			node.left.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.left
			node.left.parent = node.parent
		else:
			node.parent.right = node.left
			node.left.parent = node.parent
		bk = node.left.right
		node.left.right = node
		node.parent = node.left
		node.left = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	def _rotate_left(self, node):
		if not node.parent:
			self._tree = node.right
			node.right.parent = None
		elif AvlTree._is_left(node):
			node.parent.left = node.right
			node.right.parent = node.parent
		else:
			node.parent.right = node.right
			node.right.parent = node.parent
		bk = node.right.left
		node.right.left = node
		node.parent = node.right
		node.right = bk
		if bk:
			bk.parent = node
		node.height = max(self.get_height(node.left), self.get_height(node.right)) + 1
		node.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)
		node.num_left = 1 + self.get_num_total(node.left)

	@staticmethod
	def _get_next(node):
		if not node.right:
			return node.parent
		n = node.right
		while n.left:
			n = n.left
		return n

class SegmentTree1:

	def __init__(self, data, default=2 ** 51, func=lambda a, b: a & b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class SegmentTree:

	def __init__(self, data, default=0, func=lambda a, b: a + b):
		self._default = default
		self._func = func
		self._len = len(data)
		self._size = _size = 1 << (self._len - 1).bit_length()
		self.data = [default] * (2 * _size)
		self.data[_size:_size + self._len] = data
		for i in reversed(range(_size)):
			self.data[i] = func(self.data[i + i], self.data[i + i + 1])

	def __delitem__(self, idx):
		self[idx] = self._default

	def __getitem__(self, idx):
		return self.data[idx + self._size]

	def __setitem__(self, idx, value):
		idx += self._size
		self.data[idx] = value
		idx >>= 1
		while idx:
			self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
			idx >>= 1

	def __len__(self):
		return self._len

	def query(self, start, stop):
		if start == stop:
			return self.__getitem__(start)
		stop += 1
		start += self._size
		stop += self._size
		res = self._default
		while start < stop:
			if start & 1:
				res = self._func(res, self.data[start])
				start += 1
			if stop & 1:
				stop -= 1
				res = self._func(res, self.data[stop])
			start >>= 1
			stop >>= 1
		return res

	def __repr__(self):
		return 'SegmentTree({0})'.format(self.data)

class Factorial:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorials = [1, 1]
		self.invModulos = [0, 1]
		self.invFactorial_ = [1, 1]

	def calc(self, n):
		if n <= -1:
			print('Invalid argument to calculate n!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.factorials):
			return self.factorials[n]
		nextArr = [0] * (n + 1 - len(self.factorials))
		initialI = len(self.factorials)
		prev = self.factorials[-1]
		m = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * i % m
		self.factorials += nextArr
		return self.factorials[n]

	def inv(self, n):
		if n <= -1:
			print('Invalid argument to calculate n^(-1)')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		p = self.MOD
		pi = n % p
		if pi < len(self.invModulos):
			return self.invModulos[pi]
		nextArr = [0] * (n + 1 - len(self.invModulos))
		initialI = len(self.invModulos)
		for i in range(initialI, min(p, n + 1)):
			next = -self.invModulos[p % i] * (p // i) % p
			self.invModulos.append(next)
		return self.invModulos[pi]

	def invFactorial(self, n):
		if n <= -1:
			print('Invalid argument to calculate (n^(-1))!')
			print('n must be non-negative value. But the argument was ' + str(n))
			exit()
		if n < len(self.invFactorial_):
			return self.invFactorial_[n]
		self.inv(n)
		nextArr = [0] * (n + 1 - len(self.invFactorial_))
		initialI = len(self.invFactorial_)
		prev = self.invFactorial_[-1]
		p = self.MOD
		for i in range(initialI, n + 1):
			prev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p
		self.invFactorial_ += nextArr
		return self.invFactorial_[n]

class Combination:

	def __init__(self, MOD):
		self.MOD = MOD
		self.factorial = Factorial(MOD)

	def ncr(self, n, k):
		if k < 0 or n < k:
			return 0
		k = min(k, n - k)
		f = self.factorial
		return f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD

def powm(a, n, m):
	if a == 1 or n == 0:
		return 1
	if n % 2 == 0:
		s = powm(a, n // 2, m)
		return s * s % m
	else:
		return a * powm(a, n - 1, m) % m

def sort_list(list1, list2):
	zipped_pairs = zip(list2, list1)
	z = [x for (_, x) in sorted(zipped_pairs)]
	return z

def product(l):
	por = 1
	for i in range(len(l)):
		por *= l[i]
	return por

def binarySearchCount(arr, n, key):
	left = 0
	right = n - 1
	count = 0
	while left <= right:
		mid = int((right + left) / 2)
		if arr[mid] < key:
			count = mid + 1
			left = mid + 1
		else:
			right = mid - 1
	return count

def countdig(n):
	c = 0
	while n > 0:
		n //= 10
		c += 1
	return c

def binary(x, length):
	y = bin(x)[2:]
	return y if len(y) >= length else '0' * (length - len(y)) + y

def countGreater(arr, n, k):
	l = 0
	r = n - 1
	leftGreater = n
	while l <= r:
		m = int(l + (r - l) / 2)
		if arr[m] >= k:
			leftGreater = m
			r = m - 1
		else:
			l = m + 1
	return n - leftGreater
for ik in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	q = sorted(set(a))
	ind = defaultdict(int)
	for i in range(len(q)):
		ind[q[i]] = i
	for i in range(n):
		a[i] = ind[a[i]]
	e = [0] * (n + 2)
	s = SegmentTree(e)
	ans = 0
	for i in range(n):
		if s.query(0, a[i] - 1) <= s.query(a[i] + 1, n):
			ans += s.query(0, a[i] - 1)
		else:
			ans += s.query(a[i] + 1, n)
		s.__setitem__(a[i], e[a[i]] + 1)
		e[a[i]] += 1
	print(ans)