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
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <bits/stdc++.h>

#define ll long long
#define pi std::pair<int, int>
#define pll std::pair<ll, ll>
#define vi std::vector<int>
#define vll std::vector<ll>
#define vpi std::vector<pi>
#define vpll std::vector<pll>
#define si std::set<int>

bool test(vi &v, int tested)
{
    vi tab(v.size() + 1, 0);
    int roz = 0;
    for (int i = 0; i < v.size(); i++)
    {
        roz -= tab[i];
        if (v[i] - roz < 0 || (v[i] - roz > 0 && i + tested - 1 >= v.size()))
        {
            return false;
        }
        else if (v[i] - roz > 0)
        {
            tab[i + tested] += v[i] - roz;
            roz += tab[i + tested];
        }
    }
    return true;
}

void solve()
{
    int n;
    std::cin >> n;
    vi v(n);

    vi spf(n + 1);
    for (int i = 1; i < spf.size(); i++)
        spf[i] = i;

    for (int i = 2; i * i < spf.size(); i++)            // dla kazdej liczby mniejszej od root(n)
        if (spf[i] == i)                                // jezeli ta liczba jest pierwsza
            for (int j = i * i; j < spf.size(); j += i) // to zaczynam od i * i
                if (spf[j] == j)                        // aby ustawic liczby ktore sa poki co nazwane pierwszymi
                    spf[j] = i;                         // na liczbe i, ktora jest najmniejsza tylko dla i * i, i * (i + 1), i * (i + 2), ... no bo i * (i-1), dzieli sie przez (i-1) < i

    int max = 1;
    std::vector<bool> right(n + 1);
    right[1] = true;

    for (auto &el : v)
        std::cin >> el;

    for (int i = 2; i <= n; i++)
    {
        bool check = true;

        if (spf[i] != i)
        {
            int x = i, prev = -1;
            while (x != 1)
            {
                if (spf[x] != prev)
                {
                    if (!right[spf[x]] || !right[i / spf[x]])
                    {
                        check = false;
                        break;
                    }
                    prev = spf[x];
                }
                x /= spf[x];
            }
        }

        if (check && test(v, i))
        {
            right[i] = true;
            max = i;
        }
    }

    std::cout << max << '\n';
}

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

    int t = 1;
    // std::cin >> t;
    while (t--)
    {
        solve();
    }
}