Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ACM-ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

B. Lost Array

time limit per test

1 secondmemory limit per test

256 megabytesinput

standard inputoutput

standard outputBajtek, known for his unusual gifts, recently got an integer array $$$x_0, x_1, \ldots, x_{k-1}$$$.

Unfortunately, after a huge array-party with his extraordinary friends, he realized that he'd lost it. After hours spent on searching for a new toy, Bajtek found on the arrays producer's website another array $$$a$$$ of length $$$n + 1$$$. As a formal description of $$$a$$$ says, $$$a_0 = 0$$$ and for all other $$$i$$$ ($$$1 \le i \le n$$$) $$$a_i = x_{(i-1)\bmod k} + a_{i-1}$$$, where $$$p \bmod q$$$ denotes the remainder of division $$$p$$$ by $$$q$$$.

For example, if the $$$x = [1, 2, 3]$$$ and $$$n = 5$$$, then:

- $$$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$$$.

So, if the $$$x = [1, 2, 3]$$$ and $$$n = 5$$$, then $$$a = [0, 1, 3, 6, 7, 9]$$$.

Now the boy hopes that he will be able to restore $$$x$$$ from $$$a$$$! Knowing that $$$1 \le k \le n$$$, help him and find all possible values of $$$k$$$ — possible lengths of the lost array.

Input

The first line contains exactly one integer $$$n$$$ ($$$1 \le n \le 1000$$$) — the length of the array $$$a$$$, excluding the element $$$a_0$$$.

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^6$$$).

Note that $$$a_0$$$ is always $$$0$$$ and is not given in the input.

Output

The first line of the output should contain one integer $$$l$$$ denoting the number of correct lengths of the lost array.

The second line of the output should contain $$$l$$$ integers — possible lengths of the lost array in increasing order.

Examples

Input

5

1 2 3 4 5

Output

5

1 2 3 4 5

Input

5

1 3 5 6 8

Output

2

3 5

Input

3

1 5 3

Output

1

3

Note

In the first example, any $$$k$$$ is suitable, since $$$a$$$ is an arithmetic progression.

Possible arrays $$$x$$$:

- $$$[1]$$$
- $$$[1, 1]$$$
- $$$[1, 1, 1]$$$
- $$$[1, 1, 1, 1]$$$
- $$$[1, 1, 1, 1, 1]$$$

In the second example, Bajtek's array can have three or five elements.

Possible arrays $$$x$$$:

- $$$[1, 2, 2]$$$
- $$$[1, 2, 2, 1, 2]$$$

For example, $$$k = 4$$$ is bad, since it leads to $$$6 + x_0 = 8$$$ and $$$0 + x_0 = 1$$$, which is an obvious contradiction.

In the third example, only $$$k = n$$$ is good.

Array $$$[1, 4, -2]$$$ satisfies the requirements.

Note that $$$x_i$$$ may be negative.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/18/2018 23:26:45 (d1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|