1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <algorithm>
#include <iostream>
#include <set>
#include <vector>
#ifdef GEN
#include <cstdlib>
#include <ctime>
#include <fstream>
#endif

const int MAX = 100005;

long H[MAX];
long C[MAX];
bool isP[MAX];
std::vector<int> P;

void init(int n) {
  // Eratostenes sieve
  for (int i = 2; i <= n; ++i) isP[i] = true;
  for (int i = 2; i <= n; ++i) {
    if (isP[i]) {
      P.push_back(i);
      for (int j = 2 * i; j < MAX; j += i) isP[j] = false;
    }
  }
  std::reverse(P.begin(), P.end());
}

bool test(long k, int n) {
  // std::clog << "test " << k << std::endl;
  if (k > n) return false;
  long h = 0;
  for (int i = 0; i <= n; ++i) C[i] = 0;
  for (int i = 0; i < n; ++i) {
    h -= C[i];
    long diff = H[i] - h;
    if (diff < 0) return false;  // there are no negative waves
    if (i + k > n && diff != 0)
      return false;  // waves should not go out of boundary
    if (i + k <= n) C[i + k] = diff;
    h += diff;
  }
  h -= C[n];
  return h == 0;
}

std::vector<int> ps;
int nn;

int f(int i = 0, long k = 1) {
  if (i >= ps.size()) return k;
  int best = 1;
  if (test(k * ps[i], nn)) {
    best = std::max(best, f(i + 1, k * ps[i]));
  }
  best = std::max(best, f(i + 1, k));
  return best;
}

int solve(int n) {
  ps.clear();
  for (int p : P)
    if (test(p, n)) {
      ps.push_back(p);
      long pp = p;
      while (test(pp * p, n)) {
        pp *= p;
        ps.push_back(pp);
      }
    }
  nn = n;
  // for (int ppp : ps) std::clog << "prime: " << ppp << std::endl;
  return f();
}

#ifdef GEN

int brute(int n) {
  return 1;
  for (int i = n; i > 1; --i)
    if (test(i, n)) return i;
  return 1;
}

void gen(int t, int n, std::string dir) {
  std::clog << "tests/bur/" + dir + "/" + std::to_string(t) + ".in"
            << std::endl;
  std::ofstream in_file("tests/bur/" + dir + "/" + std::to_string(t) + ".in");
  std::ofstream out_file("tests/bur/" + dir + "/" + std::to_string(t) + ".out");
  int k = std::rand() % n + 1;
  std::clog << " :: " << k << std::endl;
  long h = 0;
  for (int i = 0; i < n; ++i) C[i] = 0;
  for (int i = 0; i < n; ++i) {
    // std::clog << h << std::endl;
    long diff = (i + k <= n) ? (std::rand() % 1000 + 1) : 0;
    for (int g = 0; g < 10 && h + diff > 1000000; ++g)
      diff = (i + k <= n) ? (std::rand() % 1000 + 1) : 0;
    if (h + diff > 100000) diff = 0;
    if (i + k <= n) C[i + k] = diff;
    h -= C[i];
    h += diff;
    H[i] = h;
  }

  in_file << n << std::endl;
  for (int i = 0; i < n; ++i) in_file << H[i] << std::endl;
  // out_file << brute(n) << std::endl;
  init(n);
  out_file << solve(n) << std::endl;
}
#endif

int main() {
  std::ios_base::sync_with_stdio(0);
#ifdef GEN
  std::srand(std::time(NULL));
  for (int i = 0; i < 10; ++i) gen(i, 100000, "big");
  return 0;
#endif

  int n;
  std::cin >> n;
  for (int i = 0; i < n; ++i) std::cin >> H[i];
  init(n);
  std::cout << solve(n) << std::endl;
  return 0;
}