Iahub is a big fan of tourists. He wants to become a tourist himself, so he planned a trip. There are n destinations on a straight road that Iahub wants to visit. Iahub starts the excursion from kilometer 0. The n destinations are described by a non-negative integers sequence a_1, a_2, ..., a_{n}. The number a_{k} represents that the kth destination is at distance a_{k} kilometers from the starting point. No two destinations are located in the same place. 

Iahub wants to visit each destination only once. Note that, crossing through a destination is not considered visiting, unless Iahub explicitly wants to visit it at that point. Also, after Iahub visits his last destination, he doesn't come back to kilometer 0, as he stops his trip at the last destination. 

The distance between destination located at kilometer x and next destination, located at kilometer y, is |x - y| kilometers. We call a "route" an order of visiting the destinations. Iahub can visit destinations in any order he wants, as long as he visits all n destinations and he doesn't visit a destination more than once. 

Iahub starts writing out on a paper all possible routes and for each of them, he notes the total distance he would walk. He's interested in the average number of kilometers he would walk by choosing a route. As he got bored of writing out all the routes, he asks you to help him.


-----Input-----

The first line contains integer n (2 ≤ n ≤ 10^5). Next line contains n distinct integers a_1, a_2, ..., a_{n} (1 ≤ a_{i} ≤ 10^7).


-----Output-----

Output two integers — the numerator and denominator of a fraction which is equal to the wanted average number. The fraction must be irreducible.


-----Examples-----
Input
3
2 3 5

Output
22 3


-----Note-----

Consider 6 possible routes:  [2, 3, 5]: total distance traveled: |2 – 0| + |3 – 2| + |5 – 3| = 5;  [2, 5, 3]: |2 – 0| + |5 – 2| + |3 – 5| = 7;  [3, 2, 5]: |3 – 0| + |2 – 3| + |5 – 2| = 7;  [3, 5, 2]: |3 – 0| + |5 – 3| + |2 – 5| = 8;  [5, 2, 3]: |5 – 0| + |2 – 5| + |3 – 2| = 9;  [5, 3, 2]: |5 – 0| + |3 – 5| + |2 – 3| = 8. 

The average travel distance is $\frac{1}{6} \cdot(5 + 7 + 7 + 8 + 9 + 8)$ = $\frac{44}{6}$ = $\frac{22}{3}$.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Mathematics

Combinatorics

Implementation


Solutions:
def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
n = int(input())
a = [int(x) for x in input().split()]
sum1 = sum(a)
sum2 = 0
sumbefore = 0
a.sort()
for i in range(n):
	sum2 += a[i] * i - sumbefore
	sumbefore += a[i]
sumtot = sum1 + 2 * sum2
k = gcd(sumtot, n)
print(sumtot // k, n // k)


def gcd(a, b):
	while b:
		(a, b) = (b, a % b)
	return a
n = int(input())
a = sorted(list(map(int, input().split())))
total_dist = 0
cur_sum = 0
cur_points = 0
for x in a[::-1]:
	total_dist += cur_sum - cur_points * x
	cur_sum += x
	cur_points += 1
total_dist *= 2
total_dist += sum(a)
high = total_dist
low = n
g = gcd(low, high)
print(high // g, low // g)


from sys import stdin
import collections
import math
n = int(stdin.readline().strip())
arr = list(map(int, stdin.readline().split()))
arr.sort()
numerator = sum(arr)
temp = 0
for i in range(n):
	temp += i * arr[i]
for i in range(n - 1, -1, -1):
	temp -= arr[n - 1 - i] * i
numerator += 2 * temp
g = math.gcd(numerator, n)
print(numerator // g, n // g)


import math

def main():
	n = int(input())
	arr = list(map(int, input().split()))
	arr.sort()
	right = sum(arr)
	left = 0
	arr.insert(0, 0)
	total = 0
	for i in range(1, n + 1):
		left += arr[i]
		total += i * arr[i] - left
		total += right - (n - i) * arr[i]
		right -= arr[i]
	g = math.gcd(max(total, n), min(total, n))
	total = total // g
	n = n // g
	print(total, n)
main()


from math import gcd
n = int(input())
l = sorted(list(map(int, input().split())))
t = sum(((i + i - n + 1) * l[i] for i in range(n)))
t = 2 * t + sum(l)
d = gcd(t, n)
print(t // d, n // d)


from math import gcd
n = int(input())
a = sorted(map(int, input().split()))
ans = 0
for i in range(n):
	ans += 2 * (i + i - n + 1) * a[i]
ans += sum(a)
tmp = gcd(ans, n)
print(ans // tmp, n // tmp)


from math import *
n = int(input())
a = sorted(list(map(int, input().split())))
b = c = sum(a)
for i in range(n):
	c -= a[i]
	b += 2 * (c - (n - 1 - i) * a[i])
print(b // gcd(b, n), n // gcd(b, n))


from fractions import *

def solve():
	n = int(input())
	a = list(map(int, input().split()))
	a.sort()
	ans1 = 0
	pres = a[0]
	for i in range(1, n):
		ans1 += i * a[i] - pres
		pres += a[i]
	ans1 *= 2
	tmp = pres + ans1
	tmp1 = n
	s = Fraction(tmp, tmp1)
	print(s.numerator, s.denominator)
solve()


import fractions
x = int(input())
a = sorted(map(int, input().split()))
z = 2 * x + 1
ans = sum(((4 * i - z) * a[i - 1] for i in range(1, x + 1, 1)))
s = fractions._gcd(ans, x)
ans //= s
x //= s
ss = []
ss.append(ans)
ss.append(x)
print(*ss)


def gcd(a, b):
	return a if b == 0 else gcd(b, a % b)
n = int(input())
l = input().split()
l = [int(i) for i in l]
l.sort()
t = sum(((i + i - n + 1) * l[i] for i in range(n)))
t = t + t + sum(l)
d = gcd(t, n)
print(t // d, n // d)


import math
n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
ans = 0
gg = 0
for i in range(n):
	ans += i * a[i] - gg
	gg += a[i]
ans = sum(a) + 2 * ans
g = math.gcd(ans, n)
ans //= g
n //= g
print(ans, n)


from math import gcd

def reduce_fraction(x, y):
	d = gcd(x, y)
	x = x // d
	y = y // d
	return (x, y)
N = int(input())
A = [int(i) for i in input().split()]
A.sort()
d0 = A[0]
sum_val = 0
for i in range(N - 1):
	m_bf = i + 2
	m_af = N - i - 1
	d = A[i + 1] - A[i]
	sum_val += m_af * (2 * m_bf - 1) * d
numerator = N * d0 + sum_val
denominator = N
(numerator, denominator) = reduce_fraction(numerator, denominator)
print(numerator, denominator)


from fractions import Fraction
while 1:
	try:
		n = int(input())
		a = list(map(int, input().split()))
		s = sum(a)
		a.sort()
		for i in range(0, n):
			s += 2 * (2 * i + 1 - n) * a[i]
		f = Fraction(s, n)
		print(f.numerator, end=' ')
		print(f.denominator)
	except EOFError:
		break


import math

def main(arr):
	arr.sort()
	n = len(arr)
	prefix = [arr[0]]
	for i in range(1, len(arr)):
		prefix.append(prefix[-1] + arr[i])
	ans = sum(arr)
	for i in range(len(arr)):
		s = 0
		if i > 0:
			s = prefix[i - 1]
		val = arr[i] * i - s + (prefix[-1] - prefix[i]) - (n - 1 - i) * arr[i]
		ans += val
	d = n
	g = math.gcd(d, ans)
	print(ans // g, d // g)
	return
n = int(input())
arr = list(map(int, input().split()))
main(arr)


import os
import sys
from io import BytesIO, IOBase
import math
from collections import Counter
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))

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():
	n = int(input())
	a = list(map(int, input().split()))
	t = 0
	a.sort()
	su = sum(a)
	for i in range(n):
		t += su - (n - i) * a[i]
		su -= a[i]
	t *= 2
	t += sum(a)
	k = gcd(t, n)
	t //= k
	n //= k
	print(t, n)
	return
main()


from fractions import gcd
n = int(input())
a = sorted([int(x) for x in input().split()])
ans = 0
l = 0
for i in range(n):
	ans += i * a[i] - l
	l += a[i]
ans = sum(a) + 2 * ans
g = gcd(ans, n)
print(ans // g, n // g)


from math import gcd
n = int(input())
a = list(map(int, input().split()))
a.sort()
sa = [0] + a
for i in range(1, n + 1):
	sa[i] += sa[i - 1]
ans = 0
for i in range(n):
	ans += (2 * i - n + 1) * a[i]
ans = ans * 2 + sum(a)
g = gcd(ans, n)
ans //= g
n //= g
print(ans, n)


def gcd(m, n):
	return m if n == 0 else gcd(n, m % n)
n = int(input())
a = sorted(map(int, input().split()))
cur = sum(a)
ans = cur
pre = 0
for i in range(n):
	cur += (i + i - n) * (a[i] - pre)
	ans += cur
	pre = a[i]
g = gcd(ans, n)
print(ans // g, n // g)


import math
n = int(input())
a = [int(x) for x in input().split()]
s = sum(a)
a = sorted(a)
(x, s1) = (0, 0)
for i in range(0, n):
	if i == 0:
		x += a[i]
		continue
	s1 = s1 + (i * a[i] - x)
	x += a[i]
s1 *= 2
ans = s + s1
gcd = math.gcd(ans, n)
print(ans // gcd, n // gcd)


def gcd(a, b):
	return gcd(b % a, a) if a else b
n = int(input())
a = sorted(map(int, input().split()))
(p, q) = (0, n)
for i in range(1, n):
	p += i * (n - i) * (a[i] - a[i - 1])
p = 2 * p + sum(a)
r = gcd(p, q)
print(p // r, q // r)


from fractions import Fraction
n = int(input())
a = [int(i) for i in input().split()]
a = sorted(a)
s = []
s.append(0)
for i in range(n):
	s.append(s[-1] + a[i])
ans = 0
for i in range(1, n + 1):
	ans += s[n] - s[i - 1] - (n - i + 1) * a[i - 1]
ans = ans * 2 + sum(a)
ans = Fraction(ans, n)
print('{0:d} {1:d}'.format(ans.numerator, ans.denominator))


def read_string():
	return input()

def read_strings(return_type=iter, split=None, skip=0):
	return return_type(input().split(split)[skip:])

def read_lines(height, return_type=iter):
	return return_type((read_string() for i in range(height)))

def read_number():
	return int(input())

def read_numbers(return_type=iter, skip=0):
	return return_type((int(i) for i in input().split()[skip:]))

def read_values(*types, array=None):
	line = input().split()
	result = []
	for (return_type, i) in zip(types, range(len(types))):
		result.append(return_type(line[i]))
	if array != None:
		(array_type, array_contained) = array
		result.append(array_type((array_contained(i) for i in line[len(types):])))
	return result

def read_array(item_type=int, return_type=iter, skip=0):
	return return_type((item_type(i) for i in input().split()[skip:]))

def read_martix(height, **args):
	return_type = args['return_type'] if 'return_type' in args else iter
	return_type_inner = args['return_type_inner'] if 'return_type_inner' in args else return_type
	return_type_outer = args['return_type_outer'] if 'return_type_outer' in args else return_type
	item_type = args['item_type'] if 'item_type' in args else int
	return return_type_outer((read_array(item_type=item_type, return_type=return_type_inner) for i in range(height)))

def read_martix_linear(width, skip=0, item_type=int, skiped=None):
	num = read_array(item_type=item_type, skip=skip)
	height = len(num) / width
	return [num[i * width:(i + 1) * width] for i in range(height)]

def gcd(n, m):
	if m == 0:
		return n
	return gcd(m, n % m)

def main():
	n = read_number()
	arr = sorted(read_numbers(list))
	sum_x = sum(arr)
	sum_xy = 0
	for i in range(1, n):
		sum_xy += (arr[i] - arr[i - 1]) * i * (n - i)
	nu = sum_x + sum_xy * 2
	de = n
	g = gcd(nu, de)
	nu //= g
	de //= g
	print(nu, de)
main()


def gcd(a, b):
	if b == 0:
		return a
	return gcd(b, a % b)
n = int(input())
a = sorted(list(map(int, input().split())), reverse=True)
k = 0
s1 = 0
s2 = 0
for i in a:
	s2 += s1 - k * i
	s1 += i
	k += 1
s2 *= 2
s2 += sum(a)
gc = gcd(s2, n)
print(s2 // gc, n // gc)


import math
t = int(input())
l = list(map(int, input().split()))
l.sort()
s = sum(l)
a = s
j = 1
m = 0
for i in l:
	s -= i
	m += s - (t - j) * i
	j += 1
x = 2 * m + a
y = math.gcd(x, t)
x //= y
t //= y
print(x, t)


import math
n = int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
k = 0
s1 = 0
s2 = 0
for i in a:
	s2 += s1 - k * i
	s1 += i
	k += 1
s2 *= 2
s2 += sum(a)
gcd = math.gcd(s2, n)
print(s2 // gcd, n // gcd)


def Euclides(n, m):
	if m == 0:
		return n
	return Euclides(m, n % m)

def Solve():
	line = input().split(' ')
	n = int(line[0])
	line = input().split(' ')
	array = [0] * n
	suma = 0
	suma_pares = 0
	for i in range(n):
		array[i] = int(line[i])
		suma += array[i]
	array.sort()
	for i in range(1, n):
		suma_pares += (array[i] - array[i - 1]) * i * (n - i)
	suma_total = suma + suma_pares * 2
	g = Euclides(suma_total, n)
	print(suma_total // g, n // g)
Solve()


from sys import stdin

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

def main():
	n = int(stdin.readline())
	ar = list(map(int, stdin.readline().split()))
	s1 = sum(ar)
	ar.sort()
	prefix = [0]
	for i in range(n):
		prefix.append(prefix[-1] + ar[i])
	s2 = 0
	for i in range(n):
		s2 += prefix[-1] - prefix[i] - ar[i] * (n - i)
	s = s1 + 2 * s2
	d = gcd(s, n)
	print(s // d, n // d)
main()


import math

def read_int():
	return int(input().strip())

def read_ints():
	return list(map(int, input().strip().split(' ')))

def solve():
	n = read_int()
	a = read_ints()
	a.sort()
	R = sum((abs(a[i] - a[0]) for i in range(1, n)))
	L = 0
	S = R + sum(a)
	for i in range(1, n):
		L += (a[i] - a[i - 1]) * i
		R -= (a[i] - a[i - 1]) * (n - i)
		S += L + R
	gcd = math.gcd(S, n)
	print(S // gcd, n // gcd)
solve()


from math import gcd
n = int(input())
a = list(map(int, input().split()))
a.sort()
s = sum(a)
current_sum = 0
s2 = 0
for i in range(n):
	s2 += a[i] * i - current_sum
	current_sum += a[i]
g = gcd(s + 2 * s2, n)
print((s + 2 * s2) // g, n // g)


from fractions import Fraction
n = int(input())
l = [int(x) for x in input().split()]
l.sort()
f = Fraction(sum([(3 - 2 * n + 4 * i) * l[i] for i in range(n)]), n)
print(f.numerator, f.denominator)


from itertools import accumulate
import math

def modinv(n, p):
	return pow(n, p - 2, p)

def main():
	n = int(input())
	arr = [int(x) for x in input().split()]
	arr.sort()
	den = n
	num = 0
	s = sum(arr)
	pre_sum = list(accumulate(arr))
	for i in range(n):
		left = 0
		right = 0
		if i > 0:
			left = pre_sum[i - 1]
		if i < n - 1:
			right = s - pre_sum[i]
		if right > 0:
			right -= arr[i] * (n - i - 1)
		if left > 0:
			left = i * arr[i] - left
		c = left + arr[i] + right
		num += c
	g = math.gcd(num, den)
	print(num // g, den // g)
py2 = round(0.5)
if py2:
	from future_builtins import ascii, filter, hex, map, oct, zip
	range = xrange
import os, sys
from io import IOBase, BytesIO
BUFSIZE = 8192

class FastIO(BytesIO):
	newlines = 0

	def __init__(self, file):
		self._file = file
		self._fd = file.fileno()
		self.writable = 'x' in file.mode or 'w' in file.mode
		self.write = super(FastIO, self).write if self.writable else None

	def _fill(self):
		s = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
		self.seek((self.tell(), self.seek(0, 2), super(FastIO, self).write(s))[0])
		return s

	def read(self):
		while self._fill():
			pass
		return super(FastIO, self).read()

	def readline(self):
		while self.newlines == 0:
			s = self._fill()
			self.newlines = s.count(b'\n') + (not s)
		self.newlines -= 1
		return super(FastIO, self).readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.getvalue())
			(self.truncate(0), self.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		if py2:
			self.write = self.buffer.write
			self.read = self.buffer.read
			self.readline = self.buffer.readline
		else:
			self.write = lambda s: self.buffer.write(s.encode('ascii'))
			self.read = lambda : self.buffer.read().decode('ascii')
			self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


import math
n = int(input())
l = [int(x) for x in input().split()]
a1 = sum(l)
a2 = n
a3 = 0
temp = 0
l.sort()
for i in range(n):
	temp += l[n - i - 1]
	a3 -= a1 - temp
	a3 += (n - i - 1) * l[n - i - 1]
a1 = a1 + a3 + a3
a4 = math.gcd(a1, a2)
print(a1 // a4, a2 // a4)


from fractions import *
n = int(input())
a = list(map(int, input().split()))
a = sorted(a)
now = a[0]
ans = 0
for i in range(1, n):
	ans += i * a[i] - now
	now = now + a[i]
ans = ans * 2 + now
s = Fraction(ans, n)
print(s.numerator, s.denominator)


import math
n = int(input())
l1 = list(map(int, input().split()))
pre_sum = [0]
l1.sort()
for item in l1:
	pre_sum.append(pre_sum[-1] + item)
numerator = 0
for i in range(n):
	numerator += l1[i] * (i + 1) - pre_sum[i] + pre_sum[n] - pre_sum[i + 1] - l1[i] * (n - 1 - i)
y = math.gcd(numerator, n)
print(numerator // y, n // y)


def gcd(n, m):
	if n % m == 0:
		return m
	return gcd(m, n % m)
n = int(eval(input()))
a = list(map(int, input().split()))
a.sort()
s = a[0]
sleft = 0
for i in range(1, len(a)):
	sleft += i * a[i] - s
	s += a[i]
tot = s + sleft * 2
print(tot // gcd(tot, n), n // gcd(tot, n))


import math
n = int(input())
arr = []
arr = [int(item) for item in input().split()]
length = len(arr)
sum2 = 0
sum = 0
for i in range(length):
	val = arr[i]
	sum2 += val
arr.sort()
pre = []
bef = 0
for i in range(length):
	sum += i * arr[i] - bef
	bef += arr[i]
sum *= 2
sum += sum2
div1 = math.gcd(sum, n)
sum //= div1
n //= div1
print(sum, ' ', n)


from math import *
n = int(input())
arr = list(map(int, input().split()))
arr.sort()
S1 = sum(arr)
sums = 0
sumsi = arr[0]
for i in range(1, n):
	sums += i * arr[i] - sumsi
	sumsi += arr[i]
S2 = sums
num = S1 + 2 * S2
den = n
while int(gcd(num, den)) != 1:
	x = gcd(num, den)
	num = num // x
	den = den // x
print(int(num), int(den))


import math
n = int(input())
arr = sorted(list((int(i) for i in input().split())))
t = sum(((i + i - n + 1) * arr[i] for i in range(n)))
t = t + t + sum(arr)
d = math.gcd(t, n)
print(t // d, n // d)


from fractions import *
n = int(input())
a = [int(x) for x in input().split()]
a.sort()
a1 = a[0]
lef_sum = 0
for i in range(1, n):
	lef_sum += a[i] * i - a1
	a1 += a[i]
lef_sum *= 2
total = lef_sum + a1
s = Fraction(total, n)
print(s.numerator, s.denominator)


import sys
from math import sqrt
import math
from fractions import Fraction
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())
sum2 = 0
sumBefore = 0
sumTot = 0
n = inp()
x = inlt()
sum1 = sum(x)
x = sorted(x)
for i in range(n):
	sum2 += x[i] * i - sumBefore
	sumBefore += x[i]
sumTot = sum1 + 2 * sum2
gcd = math.gcd(sumTot, n)
print('{} {}'.format(int(sumTot // gcd), int(n // gcd)))