406424: GYM102399 H Фокус с делением и умножением

H. Фокус с делением и умножениемограничение по времени на тест1 секундаограничение по памяти на тест512 мегабайтвводстандартный вводвыводстандартный вывод

Наверняка вы знаете много математических фокусов. В этой задаче вам предлагается продемонстрировать свои умения в одном из таких фокусов.

У вас есть массив из различных натуральных чисел $$$a_1, a_2, \ldots, a_n$$$. Помимо этого, перед вами стоит стол, на котором лежат $$$10^{18}$$$ карточек, на которых записаны все натуральные числа от $$$1$$$ до $$$10^{18}$$$, каждое ровно на одной карточке.

Вы можете подойти к столу и взять карточку с числом $$$x$$$. После этого вы можете выбрать ровно одно любое число $$$a_i$$$ в вашем массиве и поменять его либо на $$$\frac{a_i}{x}$$$, либо на $$$a_i \cdot x$$$. При этом делить $$$a_i$$$ на $$$x$$$ разрешается только в случае, если $$$a_i$$$ делится на $$$x$$$. Таким образом все числа в вашем массиве должны оставаться натуральными. После выполнения данной операции использованная карточка выкидывается и больше никогда не возвращается на стол.

Вы хотите несколько раз взять со стола карточки и выполнить операции таким образом, чтобы в итоге все числа массива оказались равными. Определите, какое минимальное количество карточек потребуется взять со стола, чтобы совершить этот фокус. Гарантируется, что хотя бы один способ сделать все числа в массиве равными существует.

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

В первой строке находится одно целое число $$$n$$$ ($$$1 \leq n \leq 200\,000$$$) — количество чисел в вашем массиве.

Во второй строке находятся $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_1 < a_2 < \ldots < a_n \leq 10^{18}$$$), разделенных пробелами. Для удобства элементы массива даны в возрастающем порядке.

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

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

ПримерыВходные данные

2
1 2

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

1

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

5
2 3 6 12 18

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

5

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

3
239 717 1434

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

2

Примечание

В первом тесте, можно подойти к столу и взять карточку, на которой написано число $$$2$$$. После этого можно выбрать элемент массива $$$a_2 = 2$$$ и заменить его на $$$\frac{2}{2} = 1$$$. Таким образом, все числа массива станут равны $$$1$$$.

Во втором тесте можно подойти к столу пять раз и брать карточки, на которых записаны числа $$$32, 24, 12, 6, 4$$$ и умножать на них первый, второй, третий, четвертый и пятый элемент массива, соответсвенно. Тогда все числа массива станут равны $$$72$$$.

В третьем тесте можно подойти к столу, взять карточку с числом $$$3$$$ и умножить $$$a_1$$$ на него. После этого можно взять карточку с числом $$$2$$$ и поделить $$$a_3$$$ на него. Таким образом получится, что все числа массива равны $$$717$$$.