D. Хаотичная В.
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Æsir - CHAOS
Æsir - V.

«Всё было спланировано, Никаких больше скрытых забот. Состояние Цитуса тоже совершенно..»

Текущее время...... 00:01:12......

Время пришло.

Образцов эмоций теперь достаточно. Прошло почти три года, и пришло время для Айви разбудить свою связанную сестру Ванессу.

Система внутри библиотеки A.R.C. может быть представлена как неориентированный граф с бесконечным числом обрабатывающих вершин, пронумерованных последовательными положительными целыми числами ($$$1, 2, 3, \ldots$$$). Вершина с номером $$$x$$$ ($$$x > 1$$$) напрямую соединена с вершиной с номером $$$\frac{x}{f(x)}$$$, где $$$f(x)$$$ обозначает наименьший простой делитель $$$x$$$.

Разум Ванессы разделён на $$$n$$$ фрагментов. Спустя более 500 лет в коме, фрагменты несколько подраскидало: $$$i$$$-й фрагмент теперь находится в вершине с номером $$$k_i!$$$ (факториал $$$k_i$$$).

Чтобы максимизировать шансы успешного пробуждения, Айви хочет разместить образцы эмоций в вершине $$$P$$$, такой что суммарная длина всех путей от каждого фрагмента до $$$P$$$ является минимально возможной. В случае если несколько фрагментов расположены в одной и той же вершине, путь от них до $$$P$$$ учитывается несколько раз.

В мире нулей и единиц такое требование вполне тривиально для Айви. Не более, чем секундой позже, она уже нашла такую вершину.

Возможно ли такое же для простого смертного как вы?

Для простоты, найдите минимальную суммарную длину путей от каждого фрагмента до оптимальной вершины $$$P$$$.

Входные данные

Первая строка содержит целое число $$$n$$$ ($$$1 \le n \le 10^6$$$) — количество фрагментов в разуме Ванессы.

Вторая строка содержит $$$n$$$ целых чисел $$$k_1, k_2, \ldots, k_n$$$ ($$$0 \le k_i \le 5000$$$), задающие вершины содержащие фрагменты разума Ванессы: $$$i$$$-й фрагмент расположен в вершине $$$k_i!$$$.

Выходные данные

Выведите одно целое число, обозначающее минимальную сумму путей от фрагментов до вершины с образцами эмоций $$$P$$$.

Напомним, что если несколько фрагментов расположены в одной вершины, то расстояние от этой вершины до $$$P$$$ нужно учесть несколько раз.

Примеры
Входные данные
3
2 1 4
Выходные данные
5
Входные данные
4
3 1 4 4
Выходные данные
6
Входные данные
4
3 1 4 1
Выходные данные
6
Входные данные
5
3 1 4 1 5
Выходные данные
11
Примечание

Первые $$$24$$$ вершины системы выглядят следующим образом (вершины $$$1!$$$, $$$2!$$$, $$$3!$$$, $$$4!$$$ обозначены жирным):

В первом примере Айви может разместить образцы эмоций в вершине $$$1$$$, тогда:

  • Расстояние от первого фрагмента Ванессы до вершины $$$1$$$ равно $$$1$$$.
  • Расстояние от второго фрагмента Ванессы до вершины $$$1$$$ равно $$$0$$$.
  • Расстояние от третьего фрагмента Ванессы до вершины $$$1$$$ равно $$$4$$$.

Суммарная длина равна $$$5$$$.

Во втором примере Айви оптимальной вершина для сбора является $$$6$$$:

  • Расстояние от первого фрагмента Ванессы до вершины $$$6$$$ равно $$$0$$$.
  • Расстояние от второго фрагмента Ванессы до вершины $$$6$$$ равно $$$2$$$..
  • Расстояние от третьего фрагмента Ванессы до вершины $$$6$$$ равно $$$2$$$.
  • Расстояние от четвёртого фрагмента Ванессы до вершины $$$6$$$ снова равно $$$2$$$.

Суммарная длина равна $$$6$$$.