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

vector<ll> brzeg;
ll n;

bool check(ll k)
{
    // cout << "k" << k << "\n";
    vector<ll> pom(n, 0);
    ll sum = 0;
    for (ll i = 0; i < n; i++)
    {
        // cout << i << " ";
        ll act = brzeg[i] - sum;
        if (act < 0)
            return false;
        if (act > 0 && i + k > n)
            return false;
        sum += act;
        if (act != 0)
            pom[i + k - 1] += -act;
        sum += pom[i];
    }
    return true;
}

ll binsearch(ll a, ll b)
{
    // cout << a << " " << b << "\n";
    if (b <= a)
        return a;
    ll mid = (a + b + 1) / 2;
    if (check(mid))
    {
        return binsearch(mid, b);
    }
    return binsearch(a, mid - 1);
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    brzeg.resize(n);
    ll sum = 0;
    for (ll i = 0; i < n; i++)
    {
        cin >> brzeg[i];
        sum += (ll)brzeg[i];
    }
    for (ll i = n; i >= 1; i--)
    {
        if (sum % i == 0)
        {
            // cout << i << "\n";

            if (check(i))
            {
                cout << i << "\n";
                break;
            }
        }
    }
}