Algorithm


B. Lost Array
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Bajtek, known for his unusual gifts, recently got an integer array x0,x1,,xk1�0,�1,…,��−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�+1. As a formal description of a says, a0=0�0=0 and for all other i (1in1≤�≤�ai=x(i1)modk+ai1��=�(�−1)mod�+��−1, where pmodq�mod� denotes the remainder of division p by q.

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

  • a0=0�0=0,
  • a1=x0mod3+a0=x0+0=1�1=�0mod3+�0=�0+0=1,
  • a2=x1mod3+a1=x1+1=3�2=�1mod3+�1=�1+1=3,
  • a3=x2mod3+a2=x2+3=6�3=�2mod3+�2=�2+3=6,
  • a4=x3mod3+a3=x0+6=7�4=�3mod3+�3=�0+6=7,
  • a5=x4mod3+a4=x1+7=9�5=�4mod3+�4=�1+7=9.

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

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

Input

The first line contains exactly one integer n (1n10001≤�≤1000) — the length of the array a, excluding the element a0�0.

The second line contains n integers a1,a2,,an�1,�2,…,�� (1ai1061≤��≤106).

Note that a0�0 is always 00 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
Copy
5
1 2 3 4 5
output
Copy
5
1 2 3 4 5
input
Copy
5
1 3 5 6 8
output
Copy
2
3 5
input
Copy
3
1 5 3
output
Copy
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,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,2,1,2][1,2,2,1,2]

For example, k=4�=4 is bad, since it leads to 6+x0=86+�0=8 and 0+x0=10+�0=1, which is an obvious contradiction.

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

Array [1,4,2][1,4,−2] satisfies the requirements.

Note that xi�� may be negative.

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming

#include <bits/stdc++.h>

using namespace std;

int const N = 1001;
int n, a[N], x[N];

int main() {
  scanf("%d", &n);
  for(int i = 1; i <= n; ++i)
    scanf("%d", a + i);

  vector<int> sol;
  for(int i = 1; i <= n; ++i) {
    x[i - 1] = a[i] - a[i - 1];
    bool ok = true;
    for(int j = 1, cnt = 0; j <= n; ++j, ++cnt) {
      if(x[cnt % i] + a[j - 1] != a[j]) {
        ok = false;
        break;
      }
    }
    if(ok)
      sol.push_back(i);
  }

  printf("%d\n", int(sol.size()));
  for(int i = 0; i < sol.size(); ++i)
    printf("%d ", sol[i]);

  return 0;
}
Copy The Code & Try With Live Editor

Input

x
+
cmd
5
1 2 3 4 5

Output

x
+
cmd
5
1 2 3 4 5
Advertisements

Demonstration


Codeforces Solution-B. Lost Array-Solution in C, C++, Java, Python

Previous
Codeforces solution 1080-B-B. Margarite and the best present codeforces solution
Next
CodeChef solution DETSCORE - Determine the Score CodeChef solution C,C+