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
#include <bits/stdc++.h>
 
using namespace std;

 
#define ll long long
#define ve vector
#define fi first
#define se second
#define pb push_back
#define all(x) begin(x), end(x)
 
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

void solve(){
    int n;
    cin >> n;
    ll sum = 0;
    ve<int> v(n);
    for(auto& i : v){
        cin >> i;
        sum += i;
    }
    ve<ll> pref(n+1, 0);
    for(int k = n; k >= 1; k--){
        if(sum%k) continue;
        bool ok = 1;
        for(int i = 1; i <= n; i++){
            int x = pref[i-1];
            x -= pref[max(0, i-k)];
            x = v[i-1] - x;
            pref[i] = pref[i - 1] + x;
            if(x < 0 || (x > 0 && i + k > n + 1)){
                ok = 0;
                break;
            }
        }
        if(ok){
            cout << k << "\n";
            return;
        }
    }
}
 
signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int T = 1;
    // cin >> T;
    while(T--){
        solve();
    }
}