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
#include "bits/stdc++.h"

#define all(v) (v).begin(), (v).end()
#define st first
#define nd second
#define pb push_back
#define printv(a) { for(auto u : a) cout<<u<<" "; cout<<"\n"; }
#define debug(x) cerr << #x << " = " << x << '\n';

using namespace std;
using ll = long long;
using pii = pair<int,int>;
using vi = vector<int>;
using si = set<int>;
using mii = map<int,int>;

vector<ll> vec;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin>>n;
    ll sum = 0;
    for(int i=0;i<n;i++){
        ll a;
        cin>>a;
        vec.pb(a);
        sum += a;
    }
    vector<ll> dziel;
    for(ll i = 1;i*i <= sum;i++){
        if(i > n) break;
        if(sum % i == 0){
            dziel.pb(i);
            if(sum / i <= n){
                dziel.pb(sum/i);
            }
        }
    }
    sort(dziel.begin(), dziel.end());
    reverse(dziel.begin(),dziel.end());

    for(ll k : dziel){
        bool dziala = true;
        ll ile_odejmujemy = 0;
        queue<pair<int,int> > q;
        for(int i=1;i<=n;i++){
            ll akt = vec[i-1] - ile_odejmujemy;
            //cout<<" dla "<<i<<endl;
            if(akt < 0){
                //cout<<" psujemy sie na "<<i<<" bo "<<vec[i-1]<<" "<<ile_odejmujemy<<endl;
                dziala = false;
                break;
            }
            if(akt != 0){
                if(i + k - 1 <= n){
                    ile_odejmujemy += akt;
                    q.push({akt, i + k - 1});
                    //cout<<" dodaje na kolejke "<<akt<<" "<<i+k-1<<endl;
                }else{
                    //cout<<" dupa na "<<i<<endl;
                    dziala = false;
                    break;
                }
            }
            auto [val, when] = q.front();
            if(when == i){
                ile_odejmujemy -= val;
                //cout<<" usuwam z kolejki "<<val<<" "<<when<<endl;
                q.pop();
            }
        }   

        if(dziala){
            cout<<k<<'\n';
            break;
        }
    }  

    return 0;
}