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
#include <cstdio>
#include <cstring>
#include <vector>

int N;
long A[2000001];
long D[2000001];

bool P[1000001];

bool sprawdz(int K)
{
  D[0] = 0;
  for (int i=1; i<=N+K; ++i) {
    D[i] = A[i] - A[i-1];
    if (i >= K) {
      D[i] += D[i-K];
    }
    if (D[i] < 0) return false;
  }
  return true;
}

int dawaj()
{
  std::vector<int> pierwsze;
  pierwsze.reserve(N);

  std::vector<bool> pierwsze_ok;
  pierwsze_ok.reserve(N);
  
  P[0] = P[1] = false;
  for (int i=2; i<=N; ++i) {
    P[i] = true;
  }
  for (int p=2; p<=N; ++p) {
    if (P[p]) {
      pierwsze.push_back(p);
      pierwsze_ok.push_back(sprawdz(p));
      int n = p;
      while ((n += p) <= N) {
        P[n] = false;
      }
    }
  }

  const int ileP = pierwsze.size();

  int best_pierwsza = 1;
  for (int ip=ileP-1; ip>=0; --ip) {
    if (pierwsze_ok[ip]) {
      best_pierwsza = pierwsze[ip];
      break;
    }
  }

  for (int K=N; K>best_pierwsza; --K) {
    if (!P[K]) { // K jest liczbą złożoną, bo pierwsze załatwiliśmy wcześniej
      bool ok = true;
      for (int ip=0; ip<ileP; ++ip) {
        int p = pierwsze[ip];
        if (p > K) break;
        if (K % p == 0 && !pierwsze_ok[ip]) {
          ok = false;
          break;
        }
      }
      if (ok && sprawdz(K)) {
        return K;
      }
    }
  }
  
  return best_pierwsza;
}

int main()
{
  memset(A, 0, sizeof A);
  scanf("%d", &N);
  for (int i=1; i<=N; ++i) {
    scanf("%ld", &A[i]);
  }
  printf("%d", dawaj());
}