← 返回题目列表

Codeforces · 980/D

D. 完美团体

中文机器翻译题面 查看原题

SaMer 为他的一个问题编写了有史以来最伟大的测试用例。对于给定的整数数组,问题要求找到该数组可以分为的最小组数,使得同一组中任何一对整数的乘积都是完全平方数。

每个整数必须恰好位于一组中。但是,组中的整数不一定必须在数组中连续。

SaMer 希望从他已有的测试用例中创建更多用例。他的测试用例有一个由 $$$n$$$ 整数组成的数组 $$$A$$$,他需要找到 $$$A$$$ 的连续子数组的数量,对于 $$$1$$$ 和 $$$n$$$(含)之间的每个整数 $$$k$$$,这些问题的答案等于 $$$k$$$。

输入

输入的第一行包含一个整数 $$$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$$$ 的连续子数组的数量。

示例

输入 #1

2
5 5

输出 #1

3 0

输入 #2

5
5 -4 2 1 8

输出 #2

5 5 3 2 0

输入 #3

1
0

输出 #3

1