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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define st first
#define nd second

ll mod = 1000000007;
ll p = 888173173;
// ll p = 2000029;
vector<ll> powers;

ll getH(vector<ll> &H, int l, int r) {
    if (l == 0) return H[r];
    ll pr;
    if (r >= H.size()) {
        pr = (H.back()*powers[r-H.size()+1])%mod;
    }
    else pr = H[r];
    return (pr-(H[l-1]*powers[r-l+1])%mod+mod)%mod;
}


bool verify(vector<int> &v, int n, int k) {
    vector<int> cancel_after(n);
    int cur = 0;
    for (int i = 0; i < n; i++) {
        if (cur > v[i]) return false;
        if (cur < v[i]) {
            if (i+k-1 >= n) return false;
            cancel_after[i+k-1] += v[i]-cur;
        }
        cur = v[i];
        cur -= cancel_after[i];
    }
    return (cur == 0);
}

void solve() {
    int n; cin >> n;
    powers.resize(n+1);
    powers[0] = 1;
    vector<int> v;
    for (int i = 1; i <= n; i++) powers[i] = (powers[i-1]*p)%mod;
    vector<int> a(n+1);
    int prev = 0;
    ll sum = 0;
    for (int i = 0; i < n; i++) {
        int x; cin >> x;
        sum += x;
        v.push_back(x);
        a[i] = x-prev;
        prev = x;
    }
    a[n] = 0-prev;
    vector<ll> H(n+1);
    H[0] = a[0];
    for (int i = 1; i <= n; i++) H[i] = (H[i-1]*p+a[i]+mod)%mod;
    for (int i = n; i>= 1; i--) {
        if (sum%i) continue;
        ll Hsum = 0;
        for (int j= 0; j < n+1; j += i) {
            Hsum += getH(H, j, j+i-1);
        }
        Hsum %=mod;
        // cout << i << ": " << Hsum << '\n';
        if (Hsum == 0 && verify(v, n, i)) {
            cout << i << '\n';
            return;
        }
    }
    cout << "1\n";
}



int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    // cin >> t;
    while (t--) {
        solve();
    }
}