The only difference between the two versions is that in this version $n \leq 1000$ and the sum of $n$ over all test cases does not exceed $1000$.

A terminal is a row of $n$ equal segments numbered $1$ to $n$ in order. There are two terminals, one above the other.

You are given an array $a$ of length $n$. For all $i = 1, 2, \dots, n$, there should be a straight wire from some point on segment $i$ of the top terminal to some point on segment $a_i$ of the bottom terminal. You can't select the endpoints of a segment. For example, the following pictures show two possible wirings if $n=7$ and $a=[4,1,4,6,7,7,5]$.

A crossing occurs when two wires share a point in common. In the picture above, crossings are circled in red.

What is the maximum number of crossings there can be if you place the wires optimally?


-----Input-----

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

The first line of each test case contains an integer $n$ ($1 \leq n \leq 1000$) — the length of the array.

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq n$) — the elements of the array.

The sum of $n$ across all test cases does not exceed $1000$.


-----Output-----

For each test case, output a single integer — the maximum number of crossings there can be if you place the wires optimally.


-----Examples-----

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


-----Note-----

The first test case is shown in the second picture in the statement.

In the second test case, the only wiring possible has the two wires cross, so the answer is $1$.

In the third test case, the only wiring possible has one wire, so the answer is $0$.

Difficulty: MEDIUM
Tags: Complete search
Skill types: Complete search

Starter code:

Solutions:
def reversePairs(nums) -> int:
	ans = 0

	def getReverse(lst):
		nonlocal ans
		if len(lst) < 2:
			return lst
		half = len(lst) // 2
		half_ = len(lst) - len(lst) // 2
		(first_half, second_half) = (getReverse(lst[:half]), getReverse(lst[half:]))
		lst = []
		i1 = 0
		i2 = 0
		while i1 < half or i2 < half_:
			if i1 == half:
				lst += second_half[i2:]
				break
			if i2 == half_:
				lst += first_half[i1:]
				ans += (half - i1) * i2
				break
			if first_half[i1] <= second_half[i2]:
				lst.append(first_half[i1])
				i1 += 1
				ans += i2
			else:
				lst.append(second_half[i2])
				i2 += 1
		return lst
	getReverse(nums)
	return ans
from collections import defaultdict
t = int(input())
for _ in range(t):
	n = int(input())
	nums = [int(x) for x in input().split()]
	tmp_lst = []
	d = defaultdict(int)
	for num in nums:
		d[num] -= 1
		tmp_lst.append((num, d[num]))
	print(reversePairs(tmp_lst))


def getsum(BITTree, i):
	s = 0
	i = i + 1
	while i > 0:
		s += BITTree[i]
		i -= i & -i
	return s

def updatebit(BITTree, n, i, v):
	i += 1
	while i <= n:
		BITTree[i] += v
		i += i & -i

def construct(arr, n):
	BITTree = [0] * (n + 1)
	for i in range(n):
		updatebit(BITTree, n, i, arr[i])
	return BITTree
for _ in range(int(input())):
	n = int(input())
	arr = [int(x) for x in input().split()]
	ar = [0] * (n + 2)
	tree = construct(ar, n + 1)
	ans = 0
	for i in range(n):
		above = i + 1
		below = arr[i]
		ans += i - getsum(tree, below - 1)
		updatebit(tree, n + 1, below, 1)
	print(ans)


from heapq import heappush, heappop
from bisect import bisect, insort

def getNumOfInversions(A):
	N = len(A)
	if N <= 1:
		return 0
	sortList = []
	result = 0
	for (i, v) in enumerate(A):
		heappush(sortList, (v, i))
	x = []
	while sortList:
		(v, i) = heappop(sortList)
		y = bisect(x, i)
		result += i - y
		insort(x, i)
	return result
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	ans = getNumOfInversions(a)
	fr = {}
	for i in range(n):
		if a[i] in fr.keys():
			fr[a[i]] += 1
		else:
			fr[a[i]] = 1
	for i in fr.keys():
		ans += fr[i] * (fr[i] - 1) // 2
	print(ans)


import sys
import bisect

def solve():
	inp = sys.stdin.readline
	n = int(inp())
	a = list(map(int, inp().split()))
	F = [0] * n
	ans = 0
	for i in range(n):
		x = n - a[i]
		while x >= 0:
			ans += F[x]
			x = (x + 1 & x) - 1
		x = n - a[i]
		while x < n:
			F[x] += 1
			x = x | x + 1
	print(ans)

def main():
	for i in range(int(sys.stdin.readline())):
		solve()
main()


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

def get():
	return int(input())

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

def S():
	for test in range(int(input())):
		solve()
import math
import itertools as it
import bisect
import time
import collections as ct

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

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

def solve():
	n = get()
	a = getint()

	def merge_sort(l, r):
		if l >= r:
			return 0
		mid = l + r >> 1
		res = merge_sort(l, mid) + merge_sort(mid + 1, r)
		i = l
		j = mid + 1
		tmp = []
		k = 0
		while i <= mid and j <= r:
			if a[i] < a[j]:
				tmp.append(a[i])
				i += 1
			else:
				tmp.append(a[j])
				res += mid - i + 1
				j += 1
		while i <= mid:
			tmp.append(a[i])
			i += 1
		while j <= r:
			tmp.append(a[j])
			j += 1
		j = 0
		for i in range(l, r + 1):
			a[i] = tmp[j]
			j += 1
		return res
	print(merge_sort(0, n - 1))
S()


import bisect
for loop in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	(l, count) = ([], 0)
	for i in range(n):
		x = bisect.bisect_left(l, a[i])
		count += len(l) - x
		bisect.insort(l, a[i])
	print(count)


import sys
input = sys.stdin.readline

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

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

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

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

def foo(n, arr):
	cross = 0
	if n <= 1:
		return 0
	mid = n // 2
	l = arr[:mid]
	r = arr[mid:]
	cross += foo(len(l), l) + foo(len(r), r)
	i = j = k = 0
	while i < len(l) and j < len(r):
		if l[i] < r[j]:
			arr[k] = l[i]
			i += 1
		else:
			arr[k] = r[j]
			j += 1
			cross += len(l) - i
		k += 1
	while i < len(l):
		arr[k] = l[i]
		i += 1
		k += 1
	while j < len(r):
		arr[k] = r[j]
		j += 1
		k += 1
	return cross
num = inp()
for i in range(num):
	line1 = inp()
	line2 = inlt()
	print(foo(line1, line2))


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	cnt = 0
	for (i, j) in enumerate(a):
		cnt += sum([1 for v in a[i + 1:] if v <= j])
	print(cnt)


t = int(input())
out = ''
for _ in range(t):
	n = int(input())
	arr = [int(x) for x in input().split()]
	passed = []
	ans = 0
	for x in arr:
		i = 0
		for i in range(len(passed)):
			if passed[i] >= x:
				break
		else:
			i += 1
		ans += len(passed) - i
		if i > len(passed):
			ans += 1
			passed.append(x)
		else:
			passed.insert(i, x)
	out += str(ans) + '\n'
print(out)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		ans += len(list(filter(lambda x: x >= a[i], a[:i])))
	print(ans)


import collections
from math import ceil, gcd, sqrt, log
INF = float('inf')
mod = 1000000007

def solve():
	n = int(input())
	A = list(map(int, input().split()))
	count = 0
	for i in range(n):
		to = A[i]
		for j in range(i):
			if A[j] >= to:
				count += 1
	print(count)
t = int(input())
while t != 0:
	solve()
	t -= 1


class Solution:

	def solve(self, a, n):
		if len(a) == 1:
			return 0
		count = 0
		for i in range(n - 1):
			for j in range(i + 1, n):
				if a[i] >= a[j]:
					count += 1
		return count
T = int(input())
while T:
	T -= 1
	n = int(input())
	a = list(map(int, input().split()))
	result = Solution().solve(a, n)
	print(result)


def main():
	t = int(input())
	for k in range(t):
		n = int(input())
		read = list(map(int, input().strip().split()))[:n]
		ans = 0
		for i in range(n):
			for j in range(i + 1, n):
				if read[i] >= read[j]:
					ans += 1
		print(ans)
main()


def solution(content, n):
	a = list(zip(range(1, n + 1), content))
	a.sort(key=lambda x: (x[1], -x[0]))
	result = 0
	for (i, (source, dest)) in enumerate(a):
		j = i - 1
		while j >= 0:
			(s, d) = a[j]
			if s > source or d == dest:
				result += 1
			j -= 1
	print(result)
t = int(input())
for i in range(t):
	n = int(input())
	content = [int(i) for i in input().split()]
	solution(content, n)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	crossings = 0
	for (i, item) in enumerate(a):
		for (j, _item) in enumerate(a[i + 1:]):
			if _item <= item:
				crossings += 1
	print(crossings)


def solve():
	terminal_size = int(input())
	connections = list(map(int, input().split(' ')))
	rtn = 0
	for i in range(len(connections)):
		for j in range(i + 1, len(connections)):
			if connections[j] <= connections[i]:
				rtn += 1
	print(rtn)
for _ in range(int(input())):
	solve()


import sys, collections
input = sys.stdin.readline

def solve(A):
	mapping = collections.defaultdict(list)
	for (i, val) in enumerate(A):
		mapping[val].append(i)
	aggregation = sorted(mapping.keys())
	ans = 0
	for (i, val) in enumerate(aggregation):
		ans += (len(mapping[val]) - 1) * len(mapping[val]) // 2
		for curr in mapping[val]:
			for j in range(i + 1, len(aggregation)):
				for x in mapping[aggregation[j]]:
					if curr > x:
						ans += 1
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	A = list(map(int, input().split()))
	print(solve(A))


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	output = 0
	for i in range(n - 1):
		cur = arr[i]
		for j in range(i + 1, n):
			if arr[j] <= cur:
				output += 1
	print(output)


t = int(input())
for nabor in range(t):
	n = int(input())
	arr = tuple(map(int, input().split()))
	counts = {}
	count = 0
	for i in arr:
		for (k, v) in counts.items():
			if k >= i:
				count += v
		try:
			counts[i] += 1
		except KeyError:
			counts[i] = 1
	print(count)


import sys

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

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

def main():
	for _ in range(int(input())):
		n = int(input())
		ls = get_ls()
		ans = 0
		for i in range(n - 1):
			for j in range(i + 1, n):
				if ls[i] >= ls[j]:
					ans += 1
		print(ans)
main()


_ = int(input())
for __ in range(_):
	n = int(input())
	arr = list(map(int, input().split()))
	out = 0
	for x in range(0, n - 1):
		a = arr[x]
		for y in range(x + 1, n):
			if arr[y] <= a:
				out += 1
	print(out)


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


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	a = tuple(map(int, input().split()))
	ans = 0
	for (i, n) in enumerate(a):
		for j in range(i + 1, len(a)):
			if a[j] < n:
				ans += 1
	h = Counter(a)
	for count in h.values():
		count -= 1
		ans += count * (count + 1) // 2
	print(ans)


import sys
input = sys.stdin.readline
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	count = 0
	for i in range(n):
		for j in range(i + 1, n):
			if a[j] <= a[i]:
				count += 1
	print(count)


i = int(input())
for u in range(i):
	n = int(input())
	arr = [int(x) for x in input().split()]
	s = 0
	for i in range(n - 1):
		x = arr[i]
		for j in range(i + 1, n):
			if arr[j] <= x:
				s += 1
	print(s)


t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		p = 0
		for j in range(i):
			if a[j] >= a[i]:
				p += 1
		ans += p
	print(ans)


from sys import stdin, stdout, setrecursionlimit
import collections
import math

def solve():
	return 0

def main():
	for _ in range(int(input())):
		n = int(input())
		l = list(map(int, input().split()))
		ans = 0
		for i in range(n):
			for j in range(i + 1, n):
				if l[i] >= l[j]:
					ans += 1
		print(ans)
	return
setrecursionlimit(10 ** 9)
input = stdin.readline
main()


t = int(input())
while t > 0:
	n = int(input())
	numbers = [int(num) for num in input().split(' ', n - 1)]
	sum = 0
	for i in range(1, len(numbers)):
		for j in range(i):
			if numbers[i] <= numbers[j]:
				sum = sum + 1
	print(sum)
	t = t - 1


t = int(input())
for _ in range(t):
	n = int(input())
	array = list(map(int, input().split()))
	count = 0
	for i in range(len(array)):
		for x in range(i + 1, len(array)):
			if array[i] >= array[x]:
				count += 1
	print(count)


import sys
input = sys.stdin.readline
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	ans = 0
	for i in range(n - 1):
		prev = a[i]
		for j in range(i + 1, n):
			cur = a[j]
			if cur <= prev:
				ans += 1
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	count = 0
	for j in range(n - 1):
		for k in range(j + 1, n):
			if a[j] >= a[k]:
				count += 1
	print(count)


t = int(input())
while t:
	n = int(input())
	arr = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		for j in range(i + 1, n):
			if arr[i] >= arr[j]:
				ans += 1
	print(ans)
	t -= 1


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


import sys
input = sys.stdin.readline

def print(x):
	sys.stdout.write(str(x) + '\n')
for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = 0
	for j in range(n):
		for k in range(j + 1, n):
			if a[j] >= a[k]:
				s += 1
	print(s)


t = int(input())
for _ in range(t):
	n = int(input())
	nums = [int(x) for x in input().split()]
	t = 0
	for (idx, num) in enumerate(nums):
		for i in range(idx + 1, n):
			new_num = nums[i]
			if new_num <= num:
				t += 1
	print(t)


import collections, sys
sys.setrecursionlimit(10 ** 6)
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		for j in range(i + 1, n):
			if a[j] <= a[i]:
				ans += 1
	print(ans)


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	ans = 0
	for i in range(n):
		for j in range(i):
			if a[j] >= a[i]:
				ans += 1
	print(ans)


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


for i in range(int(input())):
	n = int(input())
	wire = list(map(int, input().split()))
	ans = 0
	for j in range(n):
		for k in range(j):
			if wire[k] >= wire[j]:
				ans += 1
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	s = 0
	for i in range(n - 1):
		for j in range(i + 1, n):
			if a[j] <= a[i]:
				s += 1
	print(s)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split(' ')))
	inv = 0
	for alpha in range(n):
		for beta in range(alpha + 1, n):
			if a[beta] <= a[alpha]:
				inv += 1
	print(inv)


t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	sum = 0
	for j in range(n):
		for s in range(j + 1, n):
			if a[j] >= a[s]:
				sum += 1
	print(sum)


from collections import Counter
from re import L
import sys
for _ in range(int(input())):
	N = int(input())
	dest = list(map(int, input().split()))
	dest_dict = Counter(dest)
	ans = 0
	prep = [0 for i in range(N)]
	for i in dest_dict:
		ans += dest_dict[i] * (dest_dict[i] - 1) // 2
	for i in range(N):
		curr = dest[i]
		for j in range(i + 1, N):
			if dest[j] < curr:
				ans += 1
	print(ans)


t = int(input())
for _ in range(t):
	n = int(input())
	lst = [0] + list(map(int, input().split(' ')))
	x = 0
	for i in range(1, n + 1):
		for j in range(i + 1, n + 1):
			if lst[i] >= lst[j]:
				x += 1
	print(x)


t = int(input())
out = ''
for _ in range(t):
	n = int(input())
	a = [int(x) - 1 for x in input().split()]
	count = [0] * n
	ans = 0
	for x in a:
		ans += count[x]
		for i in range(x + 1):
			count[i] += 1
	out += str(ans) + '\n'
print(out)


x = int(input())
for i in range(x):
	n = int(input())
	a = list(map(int, input().split()))
	num = 0
	for j in range(len(a)):
		for k in range(j + 1, len(a), 1):
			if a[j] >= a[k]:
				num += 1
	print(num)


t = int(input())
for z in range(t):
	n = int(input())
	l = [int(i) for i in input().split(' ')]
	count = 0
	for i in range(n - 1):
		for j in range(i + 1, n):
			if l[i] >= l[j]:
				count += 1
	print(count)


from collections import defaultdict
import math
for cases in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	ans = 0
	for i in range(0, n):
		for j in range(i + 1, n):
			if l[i] >= l[j]:
				ans += 1
	print(ans)


import math
import os
import random
import re
import sys
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	count = 0
	for i in range(n):
		for j in range(i + 1, n):
			if arr[j] <= arr[i]:
				count += 1
	print(count)


cases = int(input())
c = []
for i in range(cases):
	n = int(input())
	c.append(list(map(int, input().strip().split())))
pairs = []
Dict = {}
for i in c:
	for j in range(1, len(i) + 1):
		Dict[j] = i[j - 1]
	pairs.append(Dict)
	Dict = {}
for d in pairs:
	count = 0
	for i in range(1, len(list(d.keys())) + 1):
		for j in range(i + 1, len(list(d.keys())) + 1):
			if d[j] <= d[i]:
				count += 1
	print(count)


import sys
sys.setrecursionlimit(10 ** 6)

class TreeNode:

	def __init__(self, val, col):
		self.val = val
		self.col = col
		self.ch = []

	def inord(self):
		print(self.val)
		for c in self.ch:
			c.inord()

def balcnt(root):
	if root == None:
		return [0, 0]
	allw = 0
	allb = 0
	for c in root.ch:
		(w, b) = balcnt(c)
		allw += w
		allb += b
	if root.col == 0:
		allw += 1
	else:
		allb += 1
	if allw == allb:
		cnt[0] += 1
	return [allw, allb]
t = int(input())
for tc in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	cnt = 0
	for i in range(len(a)):
		for j in range(i + 1, len(a)):
			if a[j] <= a[i]:
				cnt += 1
	print(cnt)


for t in range(int(input())):
	n = int(input())
	ans = list(map(int, input().split(' ')))
	result = [0 for _ in range(n)]
	result[0] = 0
	for i in range(1, n):
		for j in range(i):
			if ans[j] >= ans[i]:
				result[i] += 1
	print(sum(result))


def fun(n, l):
	res = 0
	j = 0
	for i in range(1, n):
		k = i
		while l[i] <= l[j] and j >= 0:
			(l[j], l[i]) = (l[i], l[j])
			(i, j) = (j, j - 1)
			res += 1
		j = k
	return res
N = int(input())
for i in range(N):
	n = int(input())
	l = list(map(int, input().split()))
	print(fun(n, l))


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


cases = int(input())
while cases:
	count = 0
	cases -= 1
	n = int(input())
	arr = list(map(int, input().split()))
	i = 0
	while i < len(arr):
		j = i + 1
		while j < len(arr):
			if arr[i] >= arr[j]:
				count += 1
			j += 1
		i += 1
	print(count)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	ans = 0
	for i in range(n):
		for j in range(i + 1, n):
			(f1, t1) = (i + 1, a[i])
			(f2, t2) = (j + 1, a[j])
			if f1 > f2:
				if t1 <= t2:
					ans += 1
			elif t2 <= t1:
				ans += 1
	print(ans)


for t in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	count = 0
	for i in range(n):
		for j in range(n):
			if i != j:
				if i <= j and a[i] >= a[j] or (i >= j and a[i] <= a[j]):
					count += 1
	print(count // 2)


for case in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	res = 0
	for i in range(n):
		top = i + 1
		bot = arr[i]
		for j in range(n):
			if i == j:
				continue
			tempTop = j + 1
			tempBot = arr[j]
			if tempTop <= top and tempBot >= bot:
				res += 1
				continue
			if tempTop >= top and tempBot <= bot:
				res += 1
				continue
	print(res // 2)