Это простая версия задачи. Единственное отличие — в этой версии задачи \(k = 0\).
Дан массив \(a_1, a_2, \ldots, a_n\) из \(n\) положительных целых чисел. Необходимо разбить его на наименьшее количество непрерывных отрезков так, чтобы ни на каком отрезке не было двух чисел (на разных позициях), произведение которых является полным квадратом.
При этом до разбиения разрешается сделать не более \(k\) раз следующую операцию: выбрать любое число в массиве и заменить его значение на произвольное целое положительное число. Но в этой версии задачи \(k = 0\), поэтому это не важно.
Какое наименьшее количество непрерывных отрезков нужно использовать, если сделать изменения оптимально?
Выходные данные
Для каждого набора входных данных выведите одно число — ответ на задачу.
Примечание
В первом наборе входных можно сделать такое разбиение:
- \([18, 6]\)
- \([2, 4]\)
- \([1]\)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
5 0
18 6 2 4 1
5 0
6 8 1 24 8
1 0
1
|
3
2
1
|