Bajtek 以其不寻常的天赋而闻名,最近得到了一个整数数组 $$$x_0, x_1, \ldots, x_{k-1}$$$。
不幸的是,在与他非凡的朋友们举行了一场盛大的阵列聚会之后,他意识到自己已经迷失了。经过几个小时寻找新玩具后,Bajtek 在数组生产商的网站上发现了另一个数组 $$$a$$$,长度为 $$$n + 1$$$。正如 $$$a$$$ 的正式描述所示,$$$a_0 = 0$$$ 以及所有其他 $$$i$$$ ($$$1 \le i \le n$$$) $$$a_i = x_{(i-1)\bmod k} + a_{i-1}$$$,其中 $$$p \bmod q$$$ 表示除以 $$$p$$$ 的余数$$$q$$$。
例如,如果 $$$x = [1, 2, 3]$$$ 且 $$$n = 5$$$,则:
- $$$a_0 = 0$$$,
- $$$a_1 = x_{0\bmod 3}+a_0=x_0+0=1$$$,
- $$$a_2 = x_{1\bmod 3}+a_1=x_1+1=3$$$,
- $$$a_3 = x_{2\bmod 3}+a_2=x_2+3=6$$$,
- $$$a_4 = x_{3\bmod 3}+a_3=x_0+6=7$$$,
- $$$a_5 = x_{4\bmod 3}+a_4=x_1+7=9$$$。
因此,如果 $$$x = [1, 2, 3]$$$ 且 $$$n = 5$$$,则 $$$a = [0, 1, 3, 6, 7, 9]$$$。
现在男孩希望他能够从$$$a$$$恢复$$$x$$$!知道 $$$1 \le k \le n$$$,帮助他找到 $$$k$$$ 的所有可能值——丢失数组的可能长度。
输入
第一行恰好包含一个整数 $$$n$$$ ($$$1 \le n \le 1000$$$) — 数组 $$$a$$$ 的长度,不包括元素 $$$a_0$$$。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^6$$$)。
请注意,$$$a_0$$$ 始终为 $$$0$$$,并且在输入中未给出。
输出
输出的第一行应包含一个整数 $$$l$$$ 表示丢失数组的正确长度的数量。
输出的第二行应包含 $$$l$$$ 整数 - 丢失数组的可能长度(按升序排列)。
示例
输入 #1
5 1 2 3 4 5
输出 #1
5 1 2 3 4 5
输入 #2
5 1 3 5 6 8
输出 #2
2 3 5
输入 #3
3 1 5 3
输出 #3
1 3
注意
在第一个示例中,任何 $$$k$$$ 都是合适的,因为 $$$a$$$ 是算术级数。
可能的数组 $$$x$$$:
- $$$[1]$$$
- $$$[1, 1]$$$
- $$$[1, 1, 1]$$$
- $$$[1, 1, 1, 1]$$$
- $$$[1, 1, 1, 1, 1]$$$
在第二个示例中,Bajtek 的数组可以包含三个或五个元素。
可能的数组 $$$x$$$:
- $$$[1, 2, 2]$$$
- $$$[1, 2, 2, 1, 2]$$$
例如,$$$k = 4$$$ 是不好的,因为它会导致 $$$6 + x_0 = 8$$$ 和 $$$0 + x_0 = 1$$$,这是一个明显的矛盾。
在第三个示例中,只有 $$$k = n$$$ 是好的。
数组 $$$[1, 4, -2]$$$ 满足要求。
请注意,$$$x_i$$$ 可能为负数。