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
#include <bits/stdc++.h>
using namespace std;
const int MX=1000100;
int n,m,mx=1,a[MX],c[77],cnt[MX];
long long b[77],sum=0;
bool w[MX];
bool solve(int l, long long ans) {
  if (l==m) {
    if (w[ans]) return false;
    if (ans<=mx) return true;
    int k=1,cur=0;
    for (; k<=n; k++) {
      long long cur=a[k-1]-(k>ans?cnt[k]:0);
      if (cur<0 || cur>a[k]) break;
      if (k+ans>n+1 && a[k]>cur) break;
      cnt[k+ans]=a[k]-cur;
    }
    if (k>n) mx=max(mx,int(ans)); else for (int j=ans; j<=n; j+=ans) w[j]=true;
    return (k>n);
  }
  bool was=false;
  for (int j=0; j<=c[l] && ans<=n; j++) {
    was|=solve(l+1,ans);
    if (!was) break;
    ans*=b[l];
  }
  return was;
}
int main() {
  scanf("%d",&n);
  assert(n<MX);
  for (int i=1; i<=n; i++) {
    scanf("%d",&a[i]);
    sum+=a[i];
  }
  for (long long i=2; i*i<=sum; i++) if (sum%i==0) {
    for (sum/=i, c[m]=1; sum%i==0; sum/=i) ++c[m];
    b[m++]=i;
  }
  if (sum>0) { b[m]=sum; c[m++]=1; }
  solve(0,1);
  printf("%lld\n",mx);
  return 0;
}