Вам дан массив \(a\) длины \(n\), который имеет специальное условие: каждый элемент в этом массиве имеет не более 7 делителей. Найдите длину кратчайшей непустой подпоследовательности этого массива, произведение элементов которой является полным квадратом.
Последовательность \(a\) является подпоследовательностью массива \(b\), если \(a\) можно получить из \(b\), удалив несколько (возможно, ноль или все) элементов.
Выходные данные
Выведите длину кратчайшей непустой подпоследовательности \(a\), произведение элементов которой является полным квадратом. Если существует несколько таких кратчайших подпоследовательностей, вы можете найти любую из них. Если такой подпоследовательности нет, выведите «-1».
Примечание
В первом примере, вы можете выбрать подпоследовательность \([1]\).
Во втором примере, вы можете выбрать подпоследовательность \([6, 6]\).
В третьем примере, вы можете выбрать подпоследовательность \([6, 15, 10]\).
В четвертом примере, такой подпоследовательности не существует.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 4 6
|
1
|
|
2
|
4
2 3 6 6
|
2
|
|
3
|
3
6 15 10
|
3
|
|
4
|
4
2 3 5 7
|
-1
|