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

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

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

SaMer хочет создать больше тестов из того теста, который у него уже есть. Его тест является массивом $$$A$$$ из $$$n$$$ целых чисел и ему необходимо найти число подмассивов $$$A$$$, состоящих из чисел, идущих в изначальном массиве последовательно, таких, что ответ на задачу для подмассива будет равен $$$k$$$, для всех $$$k$$$ от $$$1$$$ до $$$n$$$ включительно.

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

В первой строке содержится одно целое число $$$n$$$ ($$$1 \leq n \leq 5000$$$) — размер массива.

Во второй строке содержится $$$n$$$ целых чисел $$$a_1$$$,$$$a_2$$$,$$$\dots$$$,$$$a_n$$$ ($$$-10^8 \leq a_i \leq 10^8$$$) — значения чисел в массиве.

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

Выведите $$$n$$$ целых чисел, разделённых пробелами, $$$k$$$-е из которых должно быть равно числу подмассивов $$$A$$$, состоящих из чисел, идущих в изначальном массиве последовательно, ответ для которых на задачу равен $$$k$$$.

Примеры
Входные данные
2
5 5
Выходные данные
3 0
Входные данные
5
5 -4 2 1 8
Выходные данные
5 5 3 2 0
Входные данные
1
0
Выходные данные
1