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
#include <iostream>
#include <vector>

using namespace std;

typedef long long LL;

vector<int> a;
int zi[3000000], zm[3000000];

bool czyPasuje(int q)
{
    int p=0, k=0;
    int przen=0;
    for (int i=0; i<a.size(); ++i)
    {
        if (p<k && zm[p]==i)
        {
            przen-=zi[p];
            ++p;
        }
        if (a[i]<przen)
            return false;
        if (przen<a[i])
        {
            zi[k]=a[i]-przen;
            zm[k]=i+q;
            ++k;
            przen=a[i];
        }
    }
    return true;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    LL sa=0;
    int n;
    cin>>n;
    for (int i=0; i<n; ++i)
    {
        int x;
        cin>>x;
        a.push_back(x);
        sa+=x;
    }
    a.push_back(0);

    int wyn=0;
    for (int i=1; i*(LL)i<=sa && i<=n; ++i)
    {
        if (sa%i!=0)
            continue;
        int q=sa/i;
        if (q<=n && czyPasuje(q))
        {
            wyn=q;
            break;
        }
        if (czyPasuje(i))
            wyn=i;
    }
    cout<<wyn<<endl;
    return 0;
}