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
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
typedef long double ld;
#define pii pair<ll,ll>
#define vii vector<pair<ll,ll>>
#define vi vector<ll>
#define pll pair<ll, ll>
#define all(x) (x).begin(),(x).end()
#define siz(x) (ll)(x).size()
#define count_bits(x) __builtin_popcountll((x))
const ll M = 1e9+7;
const ll INF = 1e9;
//mt19937 mt;void random_start(){mt.seed(chrono::time_poll_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
typedef tree<ll, null_type, less<ll>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const ll MAXN = 1e5 + 5;

ll A[MAXN];
ll tmp[MAXN];

bool spr(ll k, ll n){
    for(ll i = 1; i <= n; ++i){
        tmp[i] = 0;
    }
    ll curr = 0;
    for(ll i = 1; i <= n; ++i){
        ll w = A[i] -curr;
        if(w < 0) return false;
        if(i > n-k+1 and w != 0) return false;
        tmp[i] = w;
        curr += w;
        curr -= (i >= k ? tmp[i-k+1] : 0);
    }
    return true;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n;
    cin >> n;
    ll S = 0;
    for(ll i = 1; i <= n; ++i){
        cin >> A[i];
        S +=  A[i];
    }
    for(ll i = n; i > 0; --i){
        if(S % i == 0){
            if(spr(i, n)){
                cout << i<< "\n";
                return 0;
            }
        }
    }
    return 0;
}