Æsir - CHAOS Æsir - V.

"Everything has been planned out. No more hidden concerns. The condition of Cytus is also perfect.

The time right now...... 00:01:12......

It's time."

The emotion samples are now sufficient. After almost 3 years, it's time for Ivy to awake her bonded sister, Vanessa.

The system inside A.R.C.'s Library core can be considered as an undirected graph with infinite number of processing nodes, numbered with all positive integers ($1, 2, 3, \ldots$). The node with a number $x$ ($x > 1$), is directly connected with a node with number $\frac{x}{f(x)}$, with $f(x)$ being the lowest prime divisor of $x$.

Vanessa's mind is divided into $n$ fragments. Due to more than 500 years of coma, the fragments have been scattered: the $i$-th fragment is now located at the node with a number $k_i!$ (a factorial of $k_i$).

To maximize the chance of successful awakening, Ivy decides to place the samples in a node $P$, so that the total length of paths from each fragment to $P$ is smallest possible. If there are multiple fragments located at the same node, the path from that node to $P$ needs to be counted multiple times.

In the world of zeros and ones, such a requirement is very simple for Ivy. Not longer than a second later, she has already figured out such a node.

But for a mere human like you, is this still possible?

For simplicity, please answer the minimal sum of paths' lengths from every fragment to the emotion samples' assembly node $P$.


-----Input-----

The first line contains an integer $n$ ($1 \le n \le 10^6$) — number of fragments of Vanessa's mind.

The second line contains $n$ integers: $k_1, k_2, \ldots, k_n$ ($0 \le k_i \le 5000$), denoting the nodes where fragments of Vanessa's mind are located: the $i$-th fragment is at the node with a number $k_i!$.


-----Output-----

Print a single integer, denoting the minimal sum of path from every fragment to the node with the emotion samples (a.k.a. node $P$).

As a reminder, if there are multiple fragments at the same node, the distance from that node to $P$ needs to be counted multiple times as well.


-----Examples-----
Input
3
2 1 4

Output
5

Input
4
3 1 4 4

Output
6

Input
4
3 1 4 1

Output
6

Input
5
3 1 4 1 5

Output
11



-----Note-----

Considering the first $24$ nodes of the system, the node network will look as follows (the nodes $1!$, $2!$, $3!$, $4!$ are drawn bold):

[Image]

For the first example, Ivy will place the emotion samples at the node $1$. From here:

  The distance from Vanessa's first fragment to the node $1$ is $1$.  The distance from Vanessa's second fragment to the node $1$ is $0$.  The distance from Vanessa's third fragment to the node $1$ is $4$. 

The total length is $5$.

For the second example, the assembly node will be $6$. From here:

  The distance from Vanessa's first fragment to the node $6$ is $0$.  The distance from Vanessa's second fragment to the node $6$ is $2$.  The distance from Vanessa's third fragment to the node $6$ is $2$.  The distance from Vanessa's fourth fragment to the node $6$ is again $2$. 

The total path length is $6$.

Difficulty: competition

Starter code:

Solutions:
T = 1
for test_no in range(T):
	MAXK = 5000
	n = int(input())
	cnt = [0] * (MAXK + 1)
	primeExponential = [[0 for j in range(MAXK + 1)] for i in range(MAXK + 1)]

	line, num = (input() + ' '), 0
	for c in line:
		if c != ' ': num = num * 10 + (ord(c) - 48)
		else:
			cnt[num] += 1
			num = 0

	for i in range(2, MAXK + 1):
		for j in range(0, MAXK + 1): primeExponential[i][j] += primeExponential[i-1][j]
		tmp, x = i, 2
		while x * x <= tmp:
			while tmp % x == 0:
				primeExponential[i][x] += 1
				tmp //= x
			x += 1
		if tmp > 1: primeExponential[i][tmp] += 1

	bestPD = [1] * (MAXK + 1)
	ans, cur = 0, 0

	for i in range(1, MAXK + 1):
		if cnt[i] == 0: continue
		for j in range(1, MAXK + 1):
			ans += primeExponential[i][j] * cnt[i]
			cur += primeExponential[i][j] * cnt[i]
			if primeExponential[i][j]: bestPD[i] = j

	frequency = [0] * (MAXK + 1)
	while max(bestPD) > 1:
		for i in range(MAXK + 1): frequency[i] = 0
		for i in range(MAXK + 1): frequency[bestPD[i]] += cnt[i]

		bestGroup = max(frequency)
		bestPrime = frequency.index(bestGroup)
		if bestGroup * 2 <= n: break
		if bestPrime == 1: break
		cur -= bestGroup
		cur += (n - bestGroup); ans = min(ans, cur)

		for i in range(MAXK + 1):
			if bestPD[i] != bestPrime: bestPD[i] = 1
			if bestPD[i] == 1: continue
			primeExponential[i][bestPD[i]] -= 1
			while bestPD[i] > 1 and primeExponential[i][bestPD[i]] == 0: bestPD[i] -= 1

	print(ans)

from sys import stdin, stdout

prime = list()
factor = list()
count = list()
dist = list()
N = 0

def find_prime():
    nonlocal prime
    for i in range(2, 5010):
        is_prime = True
        for j in prime:
            if i % j == 0:
                is_prime = False
                break
        if is_prime is True:
            prime.append(i)

def calculate_factor(max):
    nonlocal prime
    nonlocal factor
    nonlocal dist
    factor = [[0 for x in range(len(prime))] for y in range(5010)] 
    dist = [0] * (max+1)
    d = 0
    for i in range(1, max+1):
        temp = i
        factor[i] = list(factor[i-1])
        for j,x in enumerate(prime):
            while temp % x == 0:
                factor[i][j] +=1
                temp = temp / x
                d += 1
            if temp == 1:
                dist[i] = d 
                break
            
def dynamic_count():
    nonlocal count
    for i in range (1,len(count)):
        count[i] += count[i-1]

def moving(i, left, right, d, current_factor):
    nonlocal count
    nonlocal prime
    nonlocal factor
    nonlocal N
    while (factor[left][i] == factor[right][i]):
        d += ((2 * (count[right] - count[left-1])) - N) * (factor[right][i] - current_factor[i])
        current_factor[i] = factor[right][i]
        i -= 1
        if i < 0:
            return d
    d += ((2 * (count[right] - count[left-1])) - N) * (factor[left][i] - current_factor[i])
    current_factor[i] = factor[left][i]
    
    
    temp_left = right
    while temp_left >= left:
        if (factor[temp_left-1][i] != factor[right][i] or temp_left == left ) and count[right] - count[temp_left-1] > int(N/2):
            if (temp_left > left):
                d += ((2 * (count[temp_left-1] - count[left-1]))) * (factor[left][i] - current_factor[i]) 
            return moving(i, temp_left, right, d, current_factor)
        elif factor[temp_left-1][i] != factor[right][i]:
            i -= 1
            right = temp_left - 1
            if i < 0:
                return d
        temp_left -= 1
    return d

def unanem():
    nonlocal prime
    nonlocal count
    nonlocal N
    
    if count[1] > int(N/2):
        return 0
    current_factor = [0] * 5010
    if count[5000] - count[4998] > int(N/2):
        return moving(len(prime)-3, 4999, 5000, 0, current_factor)
    for i,x in enumerate(prime):
        counter = 0
        if i == 0:
            counter = count[1]
        else:
            counter = count[prime[i] - 1] - count[prime[i-1] - 1]
        if counter>int(N/2):
            return moving (i, prime[i-1], prime[i] - 1, 0 , current_factor)
    return 0

def main():
    nonlocal prime
    nonlocal factor
    nonlocal count
    nonlocal N
    nonlocal debugs
    N = int(stdin.readline())
    num_list = list(map(int, stdin.readline().split()))
    max = 0
    for i in num_list:
        if max < i:
            max = i
    
    
    count = [0] * (5010)
    for i in num_list:
        count[i] += 1
            
    find_prime()
    calculate_factor(max)
    dynamic_count()
    
    d = unanem()
    overall_dist = 0
    for i,c in enumerate(count):
        if i == max + 1:
            break
        if i == 0:
            continue
        overall_dist += (count[i] - count[i-1])*dist[i]
    print(overall_dist - d)
    

main()



import copy

M = 5003
Primes = []
Rob = [0] * M
for x in range(2,M):
	if Rob[x]==0:
		Primes.append(x)
	y = x+x
	while y<M:
		Rob[y]+=1
		y+=x

P = len(Primes)


n = int(input())
Cnt = [0] * M
for a in input().split():
	Cnt[int(a)] +=1


PF = []
PF.append( [0] * P)
s = 0

res = 0
for k in range(1, M):
	PF.append(copy.copy(PF[-1]))
	
	x = k
	for p in range(P):
		while x % Primes[p] ==0:
			PF[k][p]+=1
			x/=Primes[p]
			s+=1

	res += Cnt[k] * s
	

for i in range(M):
	while (len(PF[i])>0 and PF[i][-1]==0):
		PF[i].pop()
	

BPD = [ len(PF[i]) for i in range(M) ]


branched = 0
frequency = [0] * (P+1)
while ( max(BPD) > 0):
	
	# Find the best prime divisors:
	
	for i in range(P+1): frequency[i] = 0
	
	for i in range(M): frequency[BPD[i]] += Cnt[i]
	
	m = max(frequency)
	pr = frequency.index(m)
	
	if pr==0:
		break
	
	for i in range(M):
		if BPD[i]!=pr:
			branched += Cnt[i]
			Cnt[i] = 0
			BPD[i] = 0
	
	if branched * 2 >= n:
		break
	
	res += 2* branched - n
	
	for i in range(M):
		if (BPD[i]==0): continue
		
		if (len(PF[i])>0):
			PF[i][-1]-=1
		while (len(PF[i])>0 and PF[i][-1]==0):
			PF[i].pop()
		BPD[i] = len(PF[i])

print(res)