_"I hide in plain sight, just as you"_.

Gus Fring has earned a huge profit from Los Pollos Hermanos and he wishes to celebrate. He loves watching horse-riding, hence he bought $N$ horses.
One day he organizes a horse-riding competition to celebrate the deal with Don Eladio.

There are $N$ horses taking part in the competition with speeds of $A$_{$1$}$,$ $A$_{$2$}$,$ $...,$ $A$_{$N$} respectively. It is given that all speeds are distinct.

Multiple races are being conducted and it is not mandatory for each horse to participate in every race.

For the $i$^{$th$} horse, find the number of subsets with size $≥$ $2$ such that if a race were to be conducted between horses in this subset then the $i$^{$th$} horse would finish in the top three.

For subsets of size 2 the runner should finish either 1st or 2nd. There is no 3rd position when the size of the subset is 2.

Since the answer might be quite large, compute it, modulo $1000000007$ $(10^{9}+7)$.

------ Input: ------

First line will contain $T$, number of testcases. Then the testcases follow. 
First line of each testcase contains of a single integer $N$ denoting the number of horses.
The second line of each testcase contains $N$ space-separated integers $A$_{$1$}$,$ $A$_{$2$}$,$ $...,$$A$_{$N$}, denoting the speeds of the horses. 

------ Output: ------
For each testcase, output a single line containing $N$ space separated integers , where the $i$^{$th$} integer denotes the number of subsets of size $≥$ $2$ modulo $(10^{9}+7)$, such that the $i$^{$th$} horse finishes in the top three.

------ Constraints  ------
$1 ≤ T ≤ 5000$
$2 ≤ N ≤ 10^{5}$
$1 ≤ A[i] ≤ 10^{9}$
All speeds are distinct
Sum of N over all test cases does not exceed $5*10^{5}$

----- Sample Input 1 ------ 
	1
	4
4 2 3 1
----- Sample Output 1 ------ 
	7 7 7 6
----- explanation 1 ------ 
For the 1st horse the 7 subsets are-  $ [4,2,3,1],[4,2,3],[4,2,1],[4,3,1],[4,2],[4,1],[4,3]$  
For the 2nd horse the subsets are-  $[4,2,3,1],[4,2,3],[4,2,1],[2,3,1],[2,4],[2,1],[2,3]$ 
For the 3rd horse the subsets are-  $[4,2,3,1],[4,2,3],[3,2,1],[4,3,1],[3,2],[3,1],[4,3]$ 
For the 4th horse the subsets are-  $[1,2,3],[4,2,1],[4,3,1],[1,2],[4,1],[1,3]$

Difficulty: HARD
Tags: Sorting

Combinatorics

Mathematics

Ad-hoc
Skill types: Sorting

Starter code:

Solutions:
T = int(input())
mod = 10 ** 9 + 7
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))[:N]
	B = {}
	for i in range(N):
		B[A[i]] = i
	newresult = [0] * N
	A.sort()
	for i in range(N):
		index = B[A[i]]
		value = (pow(2, i, mod) - 1 + pow(2, i, mod) * (N - i - 1) % mod + pow(2, i, mod) * ((N - i - 1) * (N - i - 2)) // 2 % mod) % mod
		newresult[index] = value
	print(*newresult)


mod = pow(10, 9) + 7
t = int(input())
for t1 in range(0, t):
	n = int(input())
	ans = [0] * n
	l = list(map(int, input().split()))
	a = []
	for i in range(0, n):
		a.append((l[i], i))
	a.sort()
	for i in range(0, n):
		j = a[i][1]
		temp = (pow(2, i, mod) - 1) % mod + pow(2, i, mod) * (n - i - 1) % mod + pow(2, i, mod) * ((n - i - 1) * (n - i - 2)) // 2 % mod
		ans[j] = temp % mod
	print(*ans)


mod = 10 ** 9 + 7
T = int(input())
for _ in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	B = [[A[i], i] for i in range(N)]
	B.sort()
	ans = [0 for i in range(N)]
	for i in range(N):
		ind = B[i][1]
		val = (pow(2, i, mod) - 1 + pow(2, i, mod) * (N - i - 1) % mod + pow(2, i, mod) * ((N - i - 1) * (N - i - 2) // 2) % mod) % mod
		ans[ind] = val
	print(*ans)


mod = 10 ** 9 + 7

def fp(a, b):
	ans = 1
	while b > 0:
		if b & 1:
			ans = ans * a % mod
		b >>= 1
		a = a * a % mod
	return ans
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	pair = list(enumerate(arr))
	pair.sort(key=lambda x: x[1])
	ans = [0] * n
	for i in range(n):
		s = 0
		a = n - i - 1
		b = a * (a + 1) // 2
		p = fp(2, i)
		s = (s + p - 1) % mod
		s = (s + b * p % mod) % mod
		ans[pair[i][0]] = s
	print(' '.join(map(str, ans)))


import sys
mod = 10 ** 9 + 7
md = 998244353
input = lambda : sys.stdin.readline().strip()
inp = lambda : list(map(int, sys.stdin.readline().strip().split()))

def C(n, r, mod):
	if r > n:
		return 0
	num = den = 1
	for i in range(r):
		num = num * (n - i) % mod
		den = den * (i + 1) % mod
	return num * pow(den, mod - 2, mod) % mod
for _ in range(int(input())):
	(n,) = inp()
	a = [[int(i), j] for (i, j) in zip(input().split(), range(n))]
	a = sorted(a, key=lambda x: x[0])
	ans = [0] * n
	for i in range(n):
		res1 = C(n - i - 1, 2, mod) + n - i - 1
		res2 = pow(2, i, mod) - 1
		ans[a[i][1]] = (res1 * res2 + res2 + res1) % mod
	print(*ans)


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = [(a[i], i) for i in range(n)]
	b.sort()
	mod = int(1000000000.0) + 7
	count = [0 for i in range(n)]
	for i in range(n):
		c = b[i][1]
		value = (pow(2, i, mod) - 1 + pow(2, i, mod) * (n - i - 1) + pow(2, i, mod) * ((n - i - 1) * (n - i - 2) // 2) % mod) % mod
		count[c] = value
	print(*count)


import math
import sys
from collections import defaultdict as df

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

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

def li():
	return list(map(int, sys.stdin.readline().strip().split()))
mod = 10 ** 9 + 7

def power(x, y, p=mod):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
for _ in range(ini()):
	n = ini()
	l = li()
	d = {}
	for i in range(n):
		d[l[i]] = i
	m = [0 for i in range(n)]
	j = 0
	l.sort()
	for i in range(n):
		x = n - i - 1
		m[d[l[i]]] = power(2, i) * ((x * (x - 1) // 2 + x + 1) % mod) % mod - 1
	print(*m)


import sys
input = sys.stdin.readline
(inp, ip) = (lambda : int(input()), lambda : [int(w) for w in input().split()])
M = 10 ** 9 + 7
for _ in range(inp()):
	n = inp()
	x = ip()
	ind = {x[i]: i for i in range(n)}
	x.sort()
	ans = [0] * n
	for i in range(n):
		ans[ind[x[i]]] = (pow(2, i, M) * ((n - i) * (n - i - 1) // 2 + 1) - 1) % M
	print(*ans)


mod = 1000000007

def fun(n):
	ans = 1
	val = 2
	while n > 0:
		if n & 1:
			ans = val * ans % mod
		n = n >> 1
		val = val * val % mod
	return ans
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = a[:]
	a = sorted(a, reverse=True)
	d = {}
	for i in range(n):
		ans = 0
		val = (fun(n - i - 1) - 1) % mod
		ans += val
		if i > 0:
			ans = (ans + i * (val + 1)) % mod
		if i > 1:
			ans = (ans + i * (i - 1) // 2 % mod * (val + 1)) % mod
		d[a[i]] = ans
	for i in range(n):
		print(d[b[i]], end=' ')


def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p
input = __import__('sys').stdin.readline
mod = 1000000007
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	p = sorted(a)
	result = {}
	for i in range(n):
		if n - 1 - i > 2:
			result[p[i]] = pow(2, i, mod) - 1
			qqq = ncr(n - 1 - i, 2, mod) + n - 1 - i
			result[p[i]] += result[p[i]] * qqq % mod
			result[p[i]] += qqq
		else:
			result[p[i]] = pow(2, i + min(2, n - 1 - i), mod) - 1
	ans = []
	for j in a:
		ans.append(result[j] % mod)
	print(*ans)


val = 1000000007
dicti = {}
for _ in range(int(input())):
	n = int(input())
	l = [int(x) for x in input().split()]
	m = [[l[x], x] for x in range(n)]
	m.sort(reverse=True)
	if n - 1 not in dicti:
		dicti[n - 1] = pow(2, n - 1, val)
	if n <= 3:
		ans = [dicti[n - 1] - 1] * n
	else:
		ans = [0] * n
		ans[m[0][1]] = dicti[n - 1] - 1
		ans[m[1][1]] = dicti[n - 1] - 1
		ans[m[2][1]] = dicti[n - 1] - 1
	cnt = 3
	for i in range(3, n):
		if n - cnt - 1 not in dicti:
			dicti[n - cnt - 1] = pow(2, n - cnt - 1, val)
		ans[m[i][1]] = ((dicti[n - cnt - 1] % val - 1) % val + (cnt * (cnt - 1) // 2 % val + cnt) % val * dicti[n - cnt - 1] % val) % val
		cnt += 1
	print(*ans)


from collections import defaultdict
mod = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	b = a[:]
	a.sort(reverse=True)
	j = n - 1
	z = defaultdict(lambda : 0)
	for i in a:
		z[i] = j
		j -= 1
	for i in b:
		print((pow(2, z[i], mod) * (n - z[i] + (n - 1 - z[i]) * (n - 2 - z[i]) // 2) - 1) % mod, end=' ')
	print()


import sys
import math
from collections import defaultdict, Counter
input = sys.stdin.readline
mod = pow(10, 9) + 7
t = int(input())
for i in range(t):
	n = int(input())
	b = list(map(int, input().split()))
	a = sorted(b, reverse=True)
	ans = {}
	for j in range(n):
		if j <= 1:
			ans[a[j]] = (pow(2, n - 1, mod) - 1 + mod) % mod
		else:
			cur = pow(2, n - j - 1, mod)
			ans[a[j]] = (cur - 1 + mod) % mod
			ad = j * (j + 1) // 2 * cur % mod
			ans[a[j]] = (ans[a[j]] + ad) % mod
	for j in range(n):
		print(ans[b[j]], end=' ')
	print()


for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	b = a[:]
	b.sort()
	d = {}
	mod = 1000000007
	for i in range(n):
		y = i
		x = n - y - 1
		mul = 1
		if x > 1:
			mul = mul * x * (x - 1) // 2 + x
		if x == 0:
			mul = 0
		mul1 = pow(2, y, mod)
		d[b[i]] = (mul * mul1 % mod + mul1 - 1) % mod
	for i in range(n):
		k = a[i]
		print(d[k], end=' ')
	print('')


def power(x, y, p):
	res = 1
	x = x % p
	if x == 0:
		return 0
	while y > 0:
		if y & 1 == 1:
			res = res * x % p
		y = y >> 1
		x = x * x % p
	return res
m = 10 ** 9 + 7
for _ in range(int(input())):
	n = int(input())
	b = list(map(int, input().split()))
	a = list()
	a.append([0, 0])
	for i in range(n):
		a.append([b[i], i + 1])
	a.sort()
	res = [0] * (n + 1)
	for i in range(1, n + 1):
		ans = 0
		z = power(2, i - 1, m)
		ans = (ans + z - 1) % m
		ans = (ans + z * (n - i)) % m
		ans = (ans + z * ((n - i) * (n - i - 1)) // 2) % m
		res[a[i][1]] = ans
	for i in range(1, n + 1):
		print(res[i], end=' ')
	print()


import sys
input = sys.stdin.readline

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)

def lcm(a, b):
	return a * b / gcd(a, b)

def main():
	mod = 1000000007
	pow2 = []
	c = 1
	for i in range(100001):
		pow2.append(c)
		c *= 2
		c %= mod
	for _ in range(int(input())):
		n = int(input())
		a = list(map(int, input().split()))
		d = {}
		for i in range(n):
			d[a[i]] = i
		ans = [0] * n
		a.sort()
		for i in range(n):
			rem = n - i - 1
			ans[d[a[i]]] = (pow2[i] * ((rem * (rem - 1) // 2 + rem + 1) % mod) % mod - 1 + mod) % mod
		print(*ans)
	return
main()


from operator import itemgetter
modulo = 10 ** 9 + 7
t = int(input())
for _ in range(t):
	n = int(input())
	speed = list(map(int, input().split()))
	array = [(speed[i], i) for i in range(n)]
	array.sort(key=itemgetter(0))
	sol = [0] * n
	molt = 1
	for i in range(n):
		if i > 0:
			molt *= 2
			molt %= modulo
		if i == n - 2:
			sol[array[i][1]] = (molt * (n - i) - 1) % modulo
		elif i == n - 1:
			sol[array[i][1]] = (molt - 1) % modulo
		else:
			appo = ((n - i - 1) * (n - i - 2) >> 1) % modulo
			sol[array[i][1]] = (molt * (n - i + appo) - 1) % modulo
	print(' '.join([str(i) for i in sol]))