B. Потерянный массив
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Байтек, славящийся своими необычными подарками, недавно получил в подарок массив целых чисел $$$x_0, x_1, \ldots, x_{k-1}$$$.

К сожалению, после фантастической вечеринки, посвящённой этому массиву, он осознал, что он его потерял. После нескольких часов поисков новой игрушки, Байтек обнаружил на сайте производителя массива $$$x$$$ другой массив $$$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$$$ целых чисел — возможные длины потерянного массива в возрастающем порядке.

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

В первом примере возможны любые значения $$$k$$$, так как $$$a$$$ является арифметической прогрессией.

Возможны следующие массивы:

  • $$$[1]$$$
  • $$$[1, 1]$$$
  • $$$[1, 1, 1]$$$
  • $$$[1, 1, 1, 1]$$$
  • $$$[1, 1, 1, 1, 1]$$$

Во втором примере массив Байтека может содержать три или пять элементов.

Возможные массивы $$$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$$$ могут быть отрицательными.