#D2936. Lost Array
Lost Array
Lost Array
Bajtek, known for his unusual gifts, recently got an integer array x_0, x_1, …, 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 ≤ i ≤ n) a_i = x_{(i-1)mod k} + a_{i-1}, where p mod 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_{0mod 3}+a_0=x_0+0=1,
- a_2 = x_{1mod 3}+a_1=x_1+1=3,
- a_3 = x_{2mod 3}+a_2=x_2+3=6,
- a_4 = x_{3mod 3}+a_3=x_0+6=7,
- a_5 = x_{4mod 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 ≤ k ≤ 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 ≤ n ≤ 1000) — the length of the array a, excluding the element a_0.
The second line contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 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.
inputFormat
Input
The first line contains exactly one integer n (1 ≤ n ≤ 1000) — the length of the array a, excluding the element a_0.
The second line contains n integers a_1, a_2, …, a_n (1 ≤ a_i ≤ 10^6).
Note that a_0 is always 0 and is not given in the input.
outputFormat
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.
样例
5
1 2 3 4 5
5
1 2 3 4 5