You are given an array A with N positive elements A_{1}, A_{2}, \dots, A_{N}. You are also given a function S on any array C with length N defined as follow:
	
S(C) = \sum\limits_{i=1}^{N}(\dfrac{C_{i-1} + C_{i+1}}{2}-C_{i})

Note that conventionally, we define all elements outside the range of the array to have value 0. In this context, C_{0} = C_{N + 1} = 0.

Consider the following process:
Choose a permutation P of values from 1 to N uniformly randomly.
Let B be the array of N elements B_{1}, B_{2}, \dots, B_{N}, where B_{i} = A_{P_{i}}.

Define V as the expected value of |S(B)|. Find \lfloor V \rfloor.

Note : 
|X| denotes absolute value of X
\lfloor X \rfloor is the greatest integer that does not exceed X.

------ Input Format ------ 

- The first line of the input contains an integer T - the number of test cases. The test cases then follow.
- The first line of each test case contains an integer N - the size of array.
- The second line of each test case contains N integers A_{1},A_{2},\dots,A_{N} - the elements of the array.

------ Output Format ------ 

For each testcase, output \lfloor V \rfloor in a new line.

------ Constraints ------ 

$1 ≤ T ≤ 10$
$1 ≤ N ≤ 2 \cdot 10^{5}$
$1 ≤ A_{i} ≤ 2 \cdot 10^{5}$

----- Sample Input 1 ------ 
2
2
1 1
3
8 2 2
----- Sample Output 1 ------ 
1
4
----- explanation 1 ------ 
- Test case $2$:
- With $P = [1, 2, 3]$ or $P = [1, 3, 2]$, we obtain $B = [8, 2, 2]$, which has $|S(B)| = |(\frac{0 + 2}{2} - 8) + (\frac{8 + 2}{2} - 2) + (\frac{2 + 0}{2} - 2)| = 5$.
- With $P = [2, 1, 3]$ or $P = [3, 1, 2]$, we obtain $B = [2, 8, 2]$, which has $|S(B)| = |(\frac{0 + 8}{2}-2)+(\frac{2 + 2}{2}-8)+(\frac{8 + 0}{2}-2)| = 2$.
- With $P = [2, 3, 1]$ or $P = [3, 2, 1]$, we obtain $B = [2, 2, 8]$, which has $|S(B)| = |(\frac{0 + 2}{2}-2)+(\frac{2 + 8}{2}-2)+(\frac{2 + 0}{2}-8)| = 5$.

Therefore $V = \frac{5 + 5 + 2 + 2 + 5 + 5}{6} = 4$. We output $\lfloor V \rfloor = 4$.

Difficulty: HARD
Tags: Mathematics

Probability

Starter code:

Solutions:
import math as math
T = int(input())
for i in range(T):
	N = int(input())
	A_array = list(map(int, input().split()))
	print(math.floor(sum(A_array) / N))


i = input
for j in [0] * int(i()):
	i()
	(*a,) = map(int, i().split())
	print(sum(a) // len(a))


for tea in range(int(input())):
	n = int(input())
	a = [int(x) for x in input().split()]
	print(sum(a) // len(a))


import math
T = int(input())
for i in range(T):
	N = int(input())
	A = list(map(int, input().split()))
	print(math.floor(sum(A) / N))


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	if n == 1:
		print(-arr[0])
		continue
	s = (n - 1) * sum(arr)
	print(s // (n * (n - 1)))


import math

def main():
	t = int(input())
	while t > 0:
		n = int(input())
		A = [int(x) for x in input().split()]
		ss = 0
		cntt = 0
		for a in A:
			ss += (n - 1) * a
			cntt += n - 1
		print(ss // cntt)
		t -= 1
main()


t = int(input())
for _ in range(t):
	n = int(input())
	l = list(map(int, input().split()))
	print(sum(l) // n)


import math
for _ in range(int(input())):
	n = int(input())
	arr = input().split()
	arr = [int(i) for i in arr]
	print(int(sum(arr) / len(arr)))


def func():
	n = int(input())
	a = list(map(int, input().split()))
	s = 0
	for i in range(n):
		s += a[i]
	print(s // n)
t = int(input())
for i in range(t):
	func()


t = int(input())
for _ in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	x = sum(arr)
	print(x // n)


from sys import stdin

def check(n, a):
	data = sum(a)
	ans = data // n
	return ans
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(check(n, a))


for _ in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	print(int(sum(A) / N))


T = int(input())
for tc in range(T):
	n = int(input())
	arr = list(map(int, input().split()))
	print(sum(arr) // n)


import statistics as st
t = int(input())
while t:
	t -= 1
	n = int(input())
	s = list(map(int, input().split()))
	print(int(st.mean(s)))


mod = 1000000007
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(sum(a) // n)


t = int(input())
while t > 0:
	n = int(input())
	print(sum(list(map(int, input().split()))) // n)
	t -= 1


from math import floor
for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split(' ')[:n]))
	print(floor(sum(arr) / n))


t = int(input())
for _ in range(t):
	n = int(input())
	A = sum(map(int, input().split()))
	print(A // n)


def fact(n):
	if n == 1:
		return 1
	else:
		return n * fact(n - 1)
t = int(input())
while t != 0:
	t = t - 1
	n = int(input())
	a = list(map(int, input().split()))
	s1 = sum(a)
	print(s1 // n)


t = int(input(''))
while t:
	n = int(input(''))
	l = [int(item) for item in input('').split()]
	print(sum(l) // len(l))
	t = t - 1


for _ in range(int(input())):
	n = int(input())
	l = [int(x) for x in input().split()]
	s1 = sum(l)
	print(s1 // n)


k = int(input())
while k > 0:
	s = int(input())
	l = list(map(int, input().split()))
	print(sum(l) // s)
	k -= 1


try:
	import math
	for _ in range(int(input())):
		n = int(input())
		array = list(map(int, input().split()))
		ans = sum(array)
		fact = math.factorial(n)
		print(int(ans / n))
except:
	pass


import math
for i in range(int(input())):
	n = int(input())
	a = map(int, input().split())
	print(int(sum(a) / n))


for t in range(int(input())):
	N = int(input())
	A = list(map(int, input().split()))
	print(int(abs(sum(A) / N)))


import math

def weirdsum(n, arr):
	if n == 0:
		return 0
	if n == 1:
		return math.ceil(arr[0])
	sum_ = sum(arr)
	ans = sum_ // n
	if ans < 0:
		return -1 * ans
	return ans
t = int(input())
for i in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = weirdsum(n, arr)
	print(ans)


n = int(input())
for _ in range(n):
	n = int(input())
	x = list(map(int, input().split()))
	s = sum(x)
	print(s // n)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	ans = sum(arr) // n
	print(ans)


test = int(input())
while test:
	n = int(input())
	a = [int(x) for x in input().split()]
	print(sum(a) // n)
	test -= 1


t = int(input())
for i in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	print(sum(lst) // n)


for _ in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	if n == 2:
		print(sum(arr) // 2)
		continue
	print(sum(arr) // n)


from math import floor
t = int(input())
while t > 0:
	t = t - 1
	n = int(input())
	a = input().split()
	for i in range(0, n):
		a[i] = int(a[i])
	x = sum(a) / n
	print(floor(x))


from math import floor
facts = {}

def fact(x):
	if x in facts.keys():
		return facts[x]
	elif x <= 1:
		return 1
	else:
		pro = 1
		for i in range(2, x + 1):
			pro *= i
		facts[x] = pro
		return pro
for _ in range(int(input())):
	x = int(input())
	summ = sum(list(map(int, input().split())))
	ansss = summ // x
	print(ansss)


tcs = int(input())
for i in range(tcs):
	n = int(input())
	ans = sum(list(map(int, input().split()))) // n
	print(ans)


t = int(input())
for tt in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	s = 0
	for u in a:
		s += u
	ans = 0
	for r in range(n):
		p = ((n - 2) * a[r] + s) // 2
		if p < 0:
			p *= -1
		ans += p
	k = n * (n - 1)
	print(ans // k)


for tc in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = 0
	for i in a:
		s += i
	s /= n
	print(int(s))


for _ in range(int(input())):
	n = int(input())
	l = list(map(int, input().strip().split()))
	s = int(sum(l) / n)
	print(s)


import math

def mergeSort(lst, start, end):
	if start == end:
		return 0
	middle = start + (end - start) // 2
	a = mergeSort(lst, start, middle)
	b = mergeSort(lst, middle + 1, end)
	c = merge(lst, start, middle, end)
	return a + b + c

def merge(lst, start, middle, end):
	count = 0
	Llst = lst[start:middle + 1]
	Rlst = lst[middle + 1:end + 1]
	n1 = len(Llst)
	i = 0
	j = 0
	k = start
	while i < middle - start + 1 and j < end - middle:
		if Llst[i] <= Rlst[j]:
			lst[k] = Llst[i]
			i += 1
			k += 1
		else:
			count += n1 - i
			lst[k] = Rlst[j]
			j += 1
			k += 1
	while i < middle - start + 1:
		lst[k] = Llst[i]
		i += 1
		k += 1
	while j < end - middle:
		lst[k] = Rlst[j]
		j += 1
		k += 1
	return count
t = int(input())
for k in range(t):
	n = int(input())
	lst = list(map(int, input().split()))
	s = sum(lst)
	ans = s // n
	print(ans)


import sys
input = sys.stdin.readline
for t in range(int(input())):
	n = int(input())
	arr = list(map(int, input().split()))
	total = sum(arr)
	print(total // n)


for i in range(int(input())):
	a = int(input())
	b = list(map(int, input().split()))
	print(int(sum(b) // a))


for i in range(int(input())):
	n = int(input())
	l = list(map(int, input().split()))
	print(sum(l) // n)


t = int(input())
for i in range(t):
	n = int(input())
	sum = 0
	string = input()
	for wr in string.split():
		sum += int(wr)
	print(int(sum / n))


t = int(input())
while t:
	n = int(input())
	l = list(map(int, input().split()))
	s = sum(l)
	s //= n
	print(s)
	t -= 1


import math
for i in range(int(input())):
	n = int(input())
	l = sorted(list(map(int, input().split())))
	print(sum(l) // n)


for _ in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	sum = 0
	for i in a:
		sum = sum + i
	print(sum // n)


t = int(input())
for i in range(t):
	n = int(input())
	a = [int(x) for x in input().split()]
	print(sum(a) // n)


for k in range(int(input())):
	n = int(input())
	A = [int(i) for i in input().split()]
	print(sum(A) // n)


import os.path
from math import gcd, floor, ceil
from collections import *
import sys
mod = 1000000007
INF = float('inf')

def st():
	return list(sys.stdin.readline().strip())

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

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

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

def pr(n):
	return sys.stdout.write(str(n) + '\n')

def prl(n):
	return sys.stdout.write(str(n) + ' ')
if os.path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')

def solve():
	n = inp()
	l = li()
	pr(sum(l) // n)
for _ in range(inp()):
	solve()


T = int(input())
for _ in range(T):
	N = int(input())
	A = [int(a) for a in input().split()]
	print(sum(A) // N)


test_cases = int(input())
while test_cases != 0:
	n = int(input())
	lis = list(map(int, input().split()))
	count = 0
	for i in range(n):
		count += lis[i]
	print(count // n)
	test_cases -= 1


T = int(input())
for _ in range(T):
	N = int(input())
	a = list(map(int, input().split()))
	print(sum(a) // N)


import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	sum = 0
	for i in range(n):
		sum += a[i]
	print(sum // n)


t = int(input())
for _ in range(t):
	n = int(input())
	arr = [int(i) for i in input().strip().split()]
	if n == 1:
		print(arr[0])
	else:
		S = sum(arr)
		print(int(S / n))


for _ in range(int(input())):
	n = int(input())
	l = [int(i) for i in input().split()]
	print(sum(l) // n)


from statistics import mean
import sys
input = sys.stdin.readline
num_test_cases = int(input())
for test_case_ittr in range(num_test_cases):
	size = int(input())
	arr = [int(x) for x in input().split()]
	print(int(mean(arr)))


import heapq
import math
import sys
import collections
import bisect
import time
import random
import itertools
import string
from collections import Counter, defaultdict

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

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

def get_string():
	return sys.stdin.readline().strip()
for t in range(int(input())):
	n = int(input())
	arr = get_list()
	print(sum(arr) // n)


t = int(input())
for tc in range(t):
	n = int(input())
	arr = list(map(int, input().split()))
	s = sum(arr)
	print(s // n)


T = int(input())
for t in range(T):
	n = int(input())
	L = list(map(int, input().strip().split()))[:n]
	S = sum(L) // len(L)
	print(S)


try:
	T = int(input())
	while T:
		n = int(input())
		a = list(map(int, input().split()))
		sum_a = sum(a)
		res = sum_a // n
		print(int(res))
		T -= 1
except:
	pass


from math import ceil, gcd, factorial, sqrt, floor
import queue
import re
from itertools import permutations, combinations, accumulate
from collections import Counter, deque
from sys import stdin, stdout
from bisect import bisect, insort, bisect_left, insort_left
input = lambda : stdin.readline()

def sieve(n):
	prime = [True] * (n + 1)
	p = 2
	while p * p <= n:
		if prime[p] == True:
			for l1 in range(p * p, n + 1, p):
				prime[l1] = False
		p += 1
	return prime

def simplesieve(n):
	prime = [2]
	mark = [False] * (n + 1)
	for p in range(3, n + 1, 2):
		if mark[p] == False:
			prime.append(p)
			if p * p <= n:
				for l1 in range(p * p, n + 1, 2 * p):
					mark[l1] = True
	return prime

def segementedsieve(low, high):
	limit = int(sqrt(high))
	primes = simplesieve(limit)
	prime = [True] * (high - low + 1)
	for l1 in primes:
		lower = low // l1
		if lower <= 1:
			lower = l1 + l1
		elif low % l1 != 0:
			lower = lower * l1 + l1
		else:
			lower = lower * l1
		for l2 in range(lower, high + 1, l1):
			prime[l2 - low] = False
	s1 = []
	s = 0
	for l in range(low, high + 1):
		if prime[l - low]:
			s1.append(l)
	return s1

def isprime(n):
	if n == 2:
		return True
	if n % 2 == 0 or n == 1:
		return False
	for l1 in range(3, int(n ** 0.5) + 1, 2):
		if n % l1 == 0:
			return False
	return True

def binpow(s1, s2, s):
	r2 = 1
	s1 = s1 % s
	while s2 > 0:
		if s2 & 1:
			r2 = r2 * s1 % s
		s1 = s1 * s1 % s
		s2 >>= 1
	return r2

def lcm(s1, s2):
	return s1 // gcd(s1, s2) * s2

def gcdExtended(s1, s2):
	if s2 == 0:
		return (s1, 1, 0)
	(g, x1, y1) = gcdExtended(s2, s1 % s2)
	l1 = y1
	l2 = x1 - s1 // s2 * y1
	return (g, l1, l2)

def dfs(graph, s, l1):
	v = [0] * (s + 1)
	v[l1] = 1
	s1 = [l1]
	z = 0
	while s1 != []:
		l = s1.pop()
		for l1 in graph[l]:
			if v[l1] == 0:
				v[l1] = 1
				s1.append(l1)
	return 'no'

def bfs(graph, n, x, dest):
	v = [0] * (1 + n)
	d = [0] * (1 + n)
	d[x] = 0
	v[x] = 1
	q = queue.Queue()
	q.put(x)
	while not q.empty():
		z = q.get()
		for s in graph[z]:
			if v[s] == 0:
				v[s] = 1
				d[s] = d[z] + 1
				q.put(s)
	return d[dest]
prime = simplesieve(10 ** 5 + 1)
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	c = sum(a)
	print(c // n)


for i in range(int(input())):
	n = int(input())
	a = [int(i) for i in input().split()]
	s = sum(a) // n
	print(s)


t = int(input())
s = ''
for i in range(t):
	n = int(input())
	v = [0 for _ in range(n)]
	cnt = 0
	arr = list(map(int, input().split()))
	for i in range(n):
		v[i] = arr[i]
		cnt += v[i]
	print(int(cnt / n))


import itertools
import sys
import math
import bisect
from sys import stdin, stdout
from math import gcd, floor, sqrt, log
from collections import defaultdict as dd
from bisect import bisect_left as bl, bisect_right as br
from collections import Counter
from collections import defaultdict as dd
flush = lambda : stdout.flush()
stdstr = lambda : stdin.readline()
stdint = lambda : int(stdin.readline())
stdpr = lambda x: stdout.write(str(x))
stdmap = lambda : map(int, stdstr().split())
stdarr = lambda : list(map(int, stdstr().split()))
mod = 1000000007

def bf(arr):
	perms = itertools.permutations(arr)
	num = 0
	den = 0
	for i in perms:
		x = i[0] + i[-1]
		num += x
		den += 1
	num /= 2
	return num // den
for _ in range(stdint()):
	n = stdint()
	arr = stdarr()
	exp = sum(arr) // n
	print(exp)


import sys
from bisect import bisect_left as lb
from bisect import bisect_right as rb
from collections import deque
sys.setrecursionlimit(10 ** 8)
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)
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
mod = 10 ** 9 + 7
mod1 = 998244353
for _ in range(ii()):
	n = ii()
	a = il()
	s = sum(a)
	print(s // n)


import math
T = int(input())
for i in range(T):
	n = int(input())
	a = input().split(' ')
	a = [int(x) for x in a]
	print(math.floor(abs(sum(a) / n)))


import math
for _ in range(int(input())):
	n = int(input())
	a = list(map(int, input().split()))
	s = 0
	for i in range(n):
		s += a[i] * (n - 1)
	s = s / (n * (n - 1))
	s = math.floor(s)
	print(s)


def sumthisup(n, arr):
	return sum(arr) // n
t = int(input())
for i in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	print(sumthisup(n, a))