Read problems statements in Mandarin Chinese  and Russian. 
Alexandra has some distinct integer numbers a_{1},a_{2}...a_{n}.
Count number of pairs (i,j) such that:
1≤ i ≤ n
1≤ j ≤ n
a_{i} < a_{j}
 
------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.The first line of each test case contains a single integer n denoting the number of numbers Alexandra has. The second line contains n space-separated distinct integers a_{1}, a_{2}, ..., a_{n} denoting these numbers.
 
------ Output ------ 

For each test case, output a single line containing number of pairs for corresponding test case.
 
------ Constraints ------ 

$1 ≤ T ≤ 4$
$1 ≤ n ≤ 100000$
$0 ≤ a_{i} ≤ 10^{9}$
$All the a_{i} are distinct

----- Sample Input 1 ------ 
2
2
12 11
3
13 11 12
----- Sample Output 1 ------ 
1
3
----- explanation 1 ------ 
Case 1: Only one such pair of (i, j) indices exists: (2,1), since a2 1. 
Case 2: 3 possible pairs of indices: (2,1), (2,3), (3,1) .

Difficulty: EASY
Tags: Sorting
Skill types: Sorting

Starter code:

Solutions:
tests = int(input())
for test in range(tests):
	number = int(input())
	my_list = list(map(int, input().split()))
	count = 0
	for i in range(number - 1, 0, -1):
		count += i
	print(count)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	print(int(n * ((n - 1) / 2)))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	n1 = len(set(l))
	print(int(n * ((n - 1) / 2)))


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(n * (n - 1) // 2)


T = int(input())
for i in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	P = set(a)
	N = len(P)
	print(N * (N - 1) // 2)


T = int(input())
for t in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	A.sort()
	print(int((N ** 2 - N) / 2))


def sum(num):
	return num * (num + 1) // 2
T = int(input())
for i in range(T):
	N = int(input())
	arr = list(map(int, input().split()))
	print(sum(len(arr) - 1))


t = int(input())
for i in range(t):
	n = int(input())
	nums = input().split(' ')
	for j in range(n):
		nums[j] = int(nums[j])
	nums.sort()
	n_pairs = int(len(nums) * (len(nums) - 1) / 2)
	print(n_pairs)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	print(int(n * (n - 1) / 2))


for i in range(int(input())):
	a = int(input())
	l = list(map(int, input().split()))
	s = 0
	i = 1
	while i < a:
		s += i
		i += 1
	print(s)


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	s = set(l)
	m = len(s)
	print(int(m * (m - 1) / 2))


t = int(input())
for tc in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	d = n - 1
	r = d * (d + 1) // 2
	print(r)


for _ in range(int(input())):
	N = int(input())
	L = sorted(map(int, input().split()))
	(c, p) = (0, L[0])
	count = 0
	for i in L:
		if p < i:
			p = i
			c += 1
		count += c
	print(count)


for tc in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print(n * (n - 1) // 2)


for x in range(0, int(input())):
	n = int(input())
	array = set(list(map(int, input().split())))
	array = sorted(list(array))
	count = 0
	for x in range(0, n):
		count += n - x - 1
	print(count)


import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	print(math.comb(n, 2))


t = int(input())
for i in range(t):
	n = int(input()) - 1
	lst = input()
	print(n * (n + 1) // 2)


for _ in range(int(input())):
	x = int(input())
	l = list(map(int, input().split()))
	k = len(l) - 1
	print(k * (k + 1) // 2)


x = int(input())
for i in range(x):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	m = [l[0]]
	for i in l[1:]:
		if i != m[-1]:
			m.append(i)
	s = len(m)
	print(s * (s - 1) // 2)


import math
for i in range(int(input())):
	num = int(input())
	arr = list(map(int, input().split()))
	S = list(set(arr))
	S.sort()
	lst = []
	for i in range(1, len(S)):
		lst.append(i)
	print(sum(lst))


for i in range(int(input())):
	n = int(input())
	a_list = [int(x) for x in input().split()]
	a_list.sort()
	a_list.reverse()
	check = {}
	pairs = 0
	for j in range(len(a_list)):
		check[a_list[j]] = len(a_list) - 1 - j
	for v in check.values():
		pairs += v
	print(pairs)


import math
for i in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	s = list(set(arr))
	s.sort()
	l = []
	for i in range(1, len(s)):
		l.append(i)
	print(sum(l))


for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	print(n * (n - 1) // 2)


T = int(input())
total = 0
for j in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	c = len(set(a))
	total = 0
	for i in range(c - 1, 0, -1):
		total += i
	print(total)
	total = 0


def main():
	for _ in range(int(input())):
		n = int(input())
		A = list(map(int, input().split(' ')))[:n]
		print(n * (n - 1) // 2)
main()


from math import comb

def main():
	for _ in range(int(input())):
		n = int(input())
		A = list(map(int, input().split(' ')))[:n]
		print(comb(n, 2))
main()


for i in range(int(input())):
	x = int(input())
	input()
	print(int(x * (x - 1) / 2))


for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	print(int(n * (n - 1) / 2))


t = int(input())
for i in range(t):
	n = int(input())
	s = list(map(int, input().split()))
	s.sort()
	n1 = len(s) - 1
	print(n1 * (n1 + 1) // 2)


try:
	for _ in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		print(n * (n - 1) // 2)
except:
	pass


for _ in range(int(input())):
	x = int(input())
	y = len(list(map(int, input().split()))) - 1
	print(y * (y + 1) // 2)


import math
for _ in range(int(input())):
	x = int(input())
	l = list(map(int, input().split()))
	l.sort()
	s = set(l)
	a = len(s)
	if a > 1:
		print(int(math.factorial(a) / (math.factorial(2) * math.factorial(a - 2))))
	else:
		print(0)


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split()))
	k = len(a) - 1
	m = k * (k + 1) // 2
	print(m)
	t = t - 1


for _ in range(int(input())):
	n = int(input())
	arr = input()
	print(n * (n - 1) // 2)


for i in range(int(input())):
	n = int(input())
	l = (sorted(list(map(int, input().split()))),)
	pairs = 0
	for i in range(n):
		pairs = pairs + (n - i - 1)
	print(pairs)


t = int(input())
for _ in range(t):
	n = int(input())
	lis = input()
	out = 0
	for i in range(n):
		out += i
	print(out)


for _ in range(int(input())):
	x = int(input()) - 1
	input()
	print(x * (x + 1) // 2)


time = int(input())
for _ in range(time):
	num = int(input())
	liss = input()
	ou = 0
	for i in range(num):
		ou += i
	print(ou)


def myFac(var):
	result = 1
	for i in range(var, 1, -1):
		result = result * i
	return int(result)
t = int(input())
for i in range(t):
	n = int(input())
	var = input()
	res = int(n * (n - 1) / 2)
	print(res)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	a = set(a)
	a = list(a)
	k = len(a)
	print(k * (k - 1) // 2)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	a = len(set(l)) - 1
	print(a * (a + 1) // 2)


from math import comb
for _ in range(int(input())):
	x = int(input())
	l = set(map(int, input().split()))
	count = comb(len(l), 2)
	print(count)


T = int(input())
for _ in range(T):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	p = 0
	total = 0
	for i in range(1, n):
		if a[i] != a[i - 1]:
			p = i - 1
		total += p + 1
	print(total)


t = int(input())
for i in range(t):
	n = int(input())
	a = input()
	print(n * (n - 1) // 2)


for i in range(int(input())):
	n = int(input())
	a = list(map(int, input().strip().split()))[:n]
	if n == 1:
		print(0)
	else:
		print(int(n * ((n - 1) / 2)))


T = int(input())
for t in range(T):
	n = int(input())
	lst = input().split()
	lst.sort()
	count = 0
	for j in range(n):
		count += j
	print(count)


t = int(input())
for _ in range(t):
	n = int(input())
	a = sorted(map(int, input().split()))
	c = 0
	p = a[0]
	cnt = 0
	for i in a:
		if p < i:
			p = i
			c += 1
			cnt += c
	print(cnt)


for i in range(int(input())):
	n = int(input())
	list1 = list(map(int, input().split()))
	list1.sort()
	a = 0
	for i in range(n - 1, 0, -1):
		a += i
	print(a)


for t in range(int(input())):
	n = int(input())
	m = list(map(int, input().split()))
	k = n * (n - 1) // 2
	print(k)


for _ in range(int(input())):
	n = int(input())
	arr = sorted(list(map(int, input().split())))
	ans = 0
	count = {}
	for i in arr:
		count[i] = count.get(i, 0) + 1
	count = list(count.values())
	count = [i * count[i] for i in range(len(count))]
	print(sum(count))


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	print((len(set(arr)) - 1) * len(set(arr)) // 2)


def pairs():
	n = int(input())
	p = list(map(int, input().split(' ')))
	s = 0
	for i in range(1, n):
		s += i
	print(s)
for i in range(int(input())):
	pairs()


for _ in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	sum1 = 0
	for i in range(1, n):
		sum1 += i
	print(sum1)


for _ in range(int(input())):
	n = int(input())
	l1 = list(map(int, input().split()))
	if n == 1:
		print(0)
	elif n == 2:
		print(1)
	else:
		sum1 = 0
		for i in range(1, n):
			sum1 += i
		print(sum1)


t = int(input())
for i in range(t):
	n = int(input())
	arr = [int(ele) for ele in input().split()]
	print(n * (n - 1) // 2)