CF980D.Perfect Groups

SaMer has written the greatest test case of all time for one of his problems. For a given array of integers, the problem asks to find the minimum number of groups the array can be divided into, such that the product of any pair of integers in the same group is a perfect square.

Each integer must be in exactly one group. However, integers in a group do not necessarily have to be contiguous in the array.

SaMer wishes to create more cases from the test case he already has. His test case has an array $A$ of $n$ integers, and he needs to find the number of contiguous subarrays of $A$ that have an answer to the problem equal to $k$ for each integer $k$ between $1$ and $n$ (inclusive).

SaMer 为其某道题目编写了有史以来最棒的测试用例。对于给定的一个整数数组，该题要求找出将该数组划分成若干组的最少组数，使得同一组内任意两个整数的乘积均为完全平方数。

每个整数必须且仅能属于一个组；但同一组内的整数在原数组中不必连续。

SaMer 希望基于他已有的这个测试用例生成更多测试用例。他当前的测试用例包含一个长度为 $n$ 的整数数组 $A$，他需要针对每个 $k \in [1, n]$（含端点），计算出数组 $A$ 中有多少个连续子数组，其对应问题的答案恰好等于 $k$。

The first line of input contains a single integer $n$ ($1 \leq n \leq 5000$), the size of the array.

The second line contains $n$ integers $a_1$,$a_2$,$\dots$,$a_n$ ($-10^8 \leq a_i \leq 10^8$), the values of the array.

输入的第一行包含一个整数 $n$（$1 \leq n \leq 5000$），表示数组的大小。

第二行包含 $n$ 个整数 $a_1$、$a_2$、$\dots$、$a_n$（$-10^8 \leq a_i \leq 10^8$），表示数组的元素值。

Output $n$ space-separated integers, the $k$-th integer should be the number of contiguous subarrays of $A$ that have an answer to the problem equal to $k$.

输出 $n$ 个用空格分隔的整数，其中第 $k$ 个整数表示数组 $A$ 中满足该问题答案为 $k$ 的连续子数组的个数。