Иван и дома
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Иван коренной житель города Дубкинцово, и недавно он стал мэром своего города. В Дубкинцово есть большая улица, на которой в один ряд расположены $$$n$$$ домов. Высота $$$i$$$-го по счету дома на этой улице равна $$$a_i$$$ метров.

Население Дубкинцово постоянно растет, и управлять городом становится сложнее. В целях оптимизации управления Иван принял решение разбить улицу на участки, состоящие из подряд идущих домов. При этом каждый дом должен относиться ровно к одному участку.

По результатам голосования жителей на онлайн-портале города было принято решение, что участки улицы должны обладать следующим свойством: для любого подотрезка подряд идущих домов на одном участке произведение их высот не должно являться полным квадратом некоторого целого числа. Т.е. если участок состоит из домов с номерами от $$$l$$$ до $$$r$$$, то не существует таких $$$i$$$ и $$$j$$$ ($$$l \le i \le j \le r$$$), что $$$\prod_{k=i}^{j} a[k] = x^2$$$ для любого $$$x$$$. Известно, что в Дубкинцово не строят домов с высотой, равной полному квадрату некоторого числа, и поэтому улицу гарантированно можно разбить на такие участки.

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

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

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

В следующей строке дано $$$n$$$ целых чисел $$$a_1,a_2,\ldots a_n$$$ ($$$2 \le a_i \le 10^5$$$) — высоты домов в порядке следования. Гарантируется, что никакое $$$a_i$$$ не является полным квадратом целого числа.

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

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

Система оценки

В данной задаче 20 тестов, не считая тестов из условия. Каждый тест оценивается в 5 баллов.

ТестыДополнительные ограниченияКомментарии
$$$1, 2$$$Тест из условия
$$$3, 4, 5, 6$$$$$$n \le 10, a_i \le 10$$$
$$$7, 8, 9, 10$$$$$$n \le 10$$$
$$$11, 12$$$$$$2 \le a_i \le 3$$$
$$$13, 14, 15$$$Все $$$a_i$$$ простые числа
$$$16, 17, 18$$$$$$a_i \le 200$$$
$$$19, 20, 21, 22$$$

Примеры

Входные данные
5
2 5 10 2 3
Выходные данные
2
Входные данные
6
2 2 3 6 10 10
Выходные данные
4

Примечание

В первом примере можно разделить улицу на $$$2$$$ участка: $$$[2, 5]$$$ и $$$[10, 2, 3]$$$.

На первом участке будет три подотрезка из подряд идущих домов: $$$[2]$$$ — произведение высот домов равно 2, это не полный квадрат; $$$[5]$$$ — произведение высот домов равно 5, это не полный квадрат; $$$[2, 5]$$$ — произведение равно 10, это не полный квадрат.

На втором участке будет шесть подотрезков из подряд идущих домов: $$$[10]$$$, $$$[2]$$$, $$$[3]$$$, $$$[10, 2]$$$, $$$[2, 3]$$$, $$$[10, 2, 3]$$$. Произведение высот домов на каждом из отрезков не является полным квадратом.

Можно показать, что на меньшее количество участков разделить улицу нельзя.