Doremy's new city is under construction! The city can be regarded as a simple undirected graph with $n$ vertices. The $i$-th vertex has altitude $a_i$. Now Doremy is deciding which pairs of vertices should be connected with edges.

Due to economic reasons, there should be no self-loops or multiple edges in the graph.

Due to safety reasons, there should not be pairwise distinct vertices $u$, $v$, and $w$ such that $a_u \leq a_v \leq a_w$ and the edges $(u,v)$ and $(v,w)$ exist.

Under these constraints, Doremy would like to know the maximum possible number of edges in the graph. Can you help her?

Note that the constructed graph is allowed to be disconnected.


-----Input-----

The input consists of multiple test cases. The first line contains a single integer $t$ ($1\le t\le 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2 \le n \le 2\cdot 10^5$) — the number of vertices.

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1\le a_i\le 10^6$) — the altitudes of each vertex.

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


-----Output-----

For each test case, output the maximum possible number of edges in the graph.


-----Examples-----

Input
4
4
2 2 3 1
6
5 2 3 1 5 2
12
7 2 4 9 1 4 6 3 7 4 2 3
4
1000000 1000000 1000000 1000000
Output
3
9
35
2


-----Note-----

In the first test case, there can only be at most $3$ edges in the graph. A possible construction is to connect $(1,3)$, $(2,3)$, $(3,4)$. In the picture below the red number above node $i$ is $a_i$.

The following list shows all such $u$, $v$, $w$ that the edges $(u,v)$ and $(v,w)$ exist.

$u=1$, $v=3$, $w=2$;

$u=1$, $v=3$, $w=4$;

$u=2$, $v=3$, $w=1$;

$u=2$, $v=3$, $w=4$;

$u=4$, $v=3$, $w=1$;

$u=4$, $v=3$, $w=2$.

Another possible construction is to connect $(1,4)$, $(2,4)$, $(3,4)$.

An unacceptable construction is to connect $(1,3)$, $(2,3)$, $(2,4)$, $(3,4)$. Because when $u=4$, $v=2$, $w=3$, $a_u\le a_v \le a_w$ holds, and the respective edges exist.

Source: codeforces | Difficulty: MEDIUM
Tags: Graph algorithms

Greedy algorithms


Solutions:
def solve():
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	ans = n // 2
	arr1 = arr[0:n // 2]
	arr2 = arr[n // 2:]
	last = arr.count(arr1[-1])
	last1 = arr1.count(arr1[-1])
	last2 = arr2.count(arr1[-1])
	ans1 = (len(arr1) + last2) * (len(arr2) - last2)
	ans2 = (len(arr1) - last1) * (len(arr2) + last1)
	ans = max(ans, ans1, ans2)
	print(ans)
	return
for _ in range(int(input())):
	solve()


t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().strip().split()]
	a.sort()
	mid = (n - 1) // 2
	val = a[mid]
	count1 = 0
	i = mid + 1
	while i < n and a[i] == val:
		i += 1
		count1 += 1
	count2 = 0
	i = mid
	while i > -1 and a[i] == val:
		count2 += 1
		i -= 1
	m = (n + 1) // 2
	sub = count1 * count2
	ans1 = m * (n - m) - sub
	ans2 = (m + count1) * (n - m - count1)
	ans3 = (m - count2) * (n - m + count2)
	ans4 = 0
	if count1 + count2 == n:
		ans4 = min(count1, count2)
	print(max(ans1, ans2, ans3, ans4))


import sys
s = sys.stdin.read()
import math

def solve(data, lenght):
	data_list = [int(i) for i in data.split()]
	data_list.sort()
	if data_list[0] == data_list[-1]:
		print(lenght // 2)
		return
	ans = 0
	for i in range(1, lenght):
		if data_list[i] != data_list[i - 1]:
			ans = max(ans, i * (lenght - i))
	print(ans)
lines = s.split('\n')
for index in range(1, len(lines) - 2, 2):
	lenght = int(lines[index])
	data = lines[index + 1]
	solve(data, lenght)


from bisect import bisect_left
from bisect import bisect_right
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	if all(map(lambda x: x == a[0], a)):
		print(n // 2)
	else:
		l = bisect_left(a, a[n // 2])
		r = bisect_right(a, a[n // 2])
		print(max(l * (n - l), r * (n - r)))


from collections import Counter

def solve():
	n = int(input())
	nums = list(map(int, input().split()))
	snums = sorted(set(nums))
	cnums = Counter(nums)
	nums = [cnums[i] for i in snums]
	if len(nums) == 1:
		print(max(1, nums[0] // 2))
		return
	score = 0
	upto = 0
	for num in nums:
		gain = n - num - upto
		if upto <= gain:
			score += (gain - upto) * num
			upto += num
		else:
			break
	print(score)
t = int(input())
for i in range(t):
	solve()


for tcase in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	m = n // 2
	(l, r) = (m, m)
	while l >= 0 and a[l] == a[m]:
		l -= 1
	while r < n and a[m] == a[r]:
		r += 1
	print((l + 1) * (n - r) + max((r - l - 1) * max(l + 1, n - r), (r - l - 1) // 2))


import math
from collections import Counter

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

def n():
	return int(input())

def st():
	return input()
yes = 'YES'
no = 'NO'
even = 'EVEN'
odd = 'ODD'

def prefix(L):
	size = len(L)
	for i in range(1, size):
		L[i] = L[i] + L[i - 1]
	return L
for _ in range(int(input())):
	size = n()
	L = li()
	L.sort()
	s = set(L)
	if len(s) == 1:
		print(size // 2)
		continue
	C = Counter(L)
	x = 0
	a = size // 2
	for i in C.values():
		x += i
		if x >= a:
			break
	print(max((size - x) * x, (size - x + i) * (x - i)))


t = int(input())
while t > 0:
	n = int(input())
	a = list(map(int, input().split(' ')))
	a.sort()
	ans = n // 2
	for i in range(1, n):
		if a[i - 1] != a[i]:
			ans = max(ans, i * (n - i))
	print(ans)
	t -= 1


from collections import Counter
for _ in range(int(input())):
	n = int(input())
	arr = sorted(map(int, input().split()))
	ans = n // 2
	for i in range(1, n):
		if arr[i] != arr[i - 1]:
			ans = max(ans, i * (n - i))
	print(ans)


def solve():
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	m = -1
	if n % 2 == 0:
		m = a[(n - 1) // 2] / 2 + a[n // 2] / 2
	else:
		m = a[n // 2]
	l = len([el for el in a if el < m])
	b = len([el for el in a if el > m])
	mm = len([el for el in a if el == m])
	if l < b:
		l += mm
	else:
		b += mm
	if l == 0:
		print(b // 2)
	else:
		print(l * b)
t = int(input())
for _ in range(t):
	solve()


import math
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	a.sort()
	if a[0] == a[-1]:
		print(n // 2)
	else:
		m = 0
		for i in range(1, n):
			if a[i - 1] != a[i]:
				if m < i * (n - i):
					m = i * (n - i)
		print(m)


t = int(input())
for i in range(t):
	n = int(input())
	a = input()
	b = a.split()
	for j in range(n):
		b[j] = int(b[j])
	b.sort()
	x = n // 2 - 1
	y = 0
	while y == 0:
		if b[x] != b[x + 1] and x <= n - 2:
			y = 1
		else:
			x = x + 1
		if x == n - 1:
			y = 1
			x = n - 1
	s = n // 2 - 1
	d = 0
	while d == 0:
		if b[s] != b[s + 1] and s >= 0:
			d = 1
			s = s + 1
		else:
			s = s - 1
		if s == -1:
			d = 1
			s = 0
	m = x - s + 1
	if s >= n - x - 1:
		sum = s * (n - x - 1 + m)
	if s <= n - x - 1:
		sum = (s + m) * (n - x - 1)
	if s == 0 and x == n - 1:
		sum = n // 2
	print(sum)


for s in [*open(0)][2::2]:
	a = sorted(map(int, s.split()))
	n = len(a)
	ans = n // 2
	for i in range(1, n):
		if a[i] != a[i - 1]:
			ans = max(ans, i * (n - i))
	print(ans)


t = int(input())
for i in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	l.sort()
	l.append(0)
	ans = n // 2
	for i in range(n):
		if l[i] != l[i + 1]:
			p = (i + 1) * (n - i - 1)
			ans = max(ans, p)
	print(ans)


t = int(input())
for x in range(t):
	n = int(input())
	data = input().split()
	for i in range(n):
		data[i] = int(data[i])
	data.sort()
	if data[0] == data[len(data) - 1]:
		print(n // 2)
	else:
		l = []
		for i in range(1, n):
			if not data[i] == data[i - 1]:
				l.append(i)
		l.append(n)
		maximum = (n - l[0]) * l[0]
		for i in l:
			if (n - i) * i < maximum:
				break
			else:
				maximum = (n - i) * i
		print(maximum)


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	occur = {}
	for c in l:
		if c not in occur:
			occur[c] = 1
		else:
			occur[c] += 1
	nums = list(occur.keys())
	nums.sort()
	if len(nums) == 1:
		print(n // 2)
	else:
		tot = 0
		ans = 0
		for i in range(len(nums)):
			tot += occur[nums[i]]
			ans = max(ans, tot * (n - tot))
		print(ans)


for _ in range(int(input())):
	n = int(input())
	a = [int(e) for e in input().split(' ')]
	a = sorted(a)
	res = -1
	for i in range(n - 1):
		if a[i + 1] != a[i]:
			res = max(res, (i + 1) * (n - i - 1))
	if res == -1:
		print(n // 2)
	else:
		print(res)


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.strip())

def invr():
	return map(int, input().split())
for _ in range(inp()):
	n = inp()
	arr = inlt()
	arr.sort(reverse=True)
	left = n
	i = 0
	mx = 0
	while i < n:
		cur = arr[i]
		while i < n and arr[i] == cur:
			i += 1
		mx = max(mx, i * (n - i))
	if mx == 0:
		mx = n // 2
	print(mx)


import math
t = int(input())
for _ in range(t):
	n = int(input())
	a = [int(i) for i in input().split()]
	a.sort()
	b = []
	l = a[0]
	s = 1
	for i in range(1, n):
		if a[i] == l:
			s += 1
		else:
			b.append(s)
			s = 1
		l = a[i]
	b.append(s)
	if len(b) == 1:
		print(n // 2)
		continue
	bb = b[0]
	s = n - bb
	ans = bb * s
	for j in range(1, len(b) - 1):
		bb += b[j]
		s -= b[j]
		if bb * s > ans:
			ans = bb * s
	print(ans)


for _ in range(int(input())):
	m = dict()
	n = int(input())
	s = list(map(int, input().split()))
	for i in s:
		if i not in m:
			m[i] = 1
		else:
			m[i] += 1
	s = list(set(s))
	s.sort()
	k = len(s) - 1
	ans = n // 2
	l = n
	r = 0
	for i in range(k, 0, -1):
		l -= m[s[i]]
		r += m[s[i]]
		ans = max(ans, l * r)
	print(ans)


from itertools import groupby
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	groups = []
	for (k, g) in groupby(a):
		groups.append(len(list(g)))
	if len(groups) == 1:
		print(n // 2)
	else:
		N = len(groups)
		S = 0
		m = 1000000
		for x in groups:
			if abs(S - n / 2) < m:
				m = abs(S - n / 2)
			S += x
		answer = n ** 2 / 4 - m ** 2
		print(int(answer))


q = int(input())
for o in range(q):
	n = int(input())
	a = list(map(int, input().strip().split()))
	occur = {}
	for c in a:
		if c not in occur:
			occur[c] = 1
		else:
			occur[c] += 1
	nums = list(occur.keys())
	nums.sort()
	if len(nums) == 1:
		print(n // 2)
	else:
		tot = 0
		ans = 0
		for i in range(len(nums)):
			tot += occur[nums[i]]
			ans = max(ans, tot * (n - tot))
		print(ans)


T = int(input(''))
for i in range(T):
	n = int(input(''))
	str_in = input('')
	a = [int(c) for c in str_in.split()]
	a = sorted(a, reverse=True)
	l1 = [1]
	j = 0
	for k in range(len(a)):
		if k == 0:
			l1[j] = 1
		elif a[k] == a[k - 1]:
			l1[j] += 1
		else:
			j += 1
			l1.append(1 + l1[j - 1])
	good = l1[0]
	if len(l1) == 1:
		print(len(a) // 2)
	else:
		for element in l1:
			if abs(element - n / 2) < abs(good - n / 2):
				good = element
		print(good * (n - good))


import math
from collections import Counter as C
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	c = C(a).most_common()
	c.sort(key=lambda x: x[0])
	s = 0
	left = sum([i[1] for i in c])
	ans = left // 2
	for (n, cnt) in c:
		s += cnt
		left -= cnt
		ans = max(ans, s * left)
	print(ans)


from itertools import groupby
for (n, xs) in ((int(input()), map(int, input().split())) for _ in range(int(input()))):
	(res, prefix, xs) = (0, 0, [len(list(x)) for (_, x) in groupby(sorted(xs), lambda x: x)])
	for x in xs:
		res = max(res, prefix * (n - prefix), (prefix + x) * (n - prefix - x), prefix * (n - prefix - x) + x // 2)
		prefix += x
	print(res)


import sys

def solve():
	inp = sys.stdin.readline
	n = int(inp())
	a = list(map(int, inp().split()))
	a.sort()
	i = 0
	g = []
	while i < n:
		j = i + 1
		while j < n and a[j] == a[i]:
			j += 1
		g.append(j - i)
		i = j
	if len(g) == 1:
		print(n // 2)
		return
	right = n
	left = 0
	ans = 0
	for i in range(len(g)):
		v = g[i]
		for j in range(g[i] + 1):
			ans = max(ans, left * (right - j) + j * (right - v))
		left += v
		right -= v
	print(ans)

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