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
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
#include <bits/stdc++.h>
using namespace std;

int dest[100007];
int pref[100007];

int nast[100007];

bool sito[100007];

void print(const vector<int>& v) {
    for (int x: v) {
        cerr << x << " ";
    }
    cerr << "\n";
}

void clear(int n) {
    for (int i = 1; i <= n; i++) {
        pref[i] = 0;
    }
}

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

    int n;
    cin >> n;
    
    // <gdzie, ile>
    queue<pair<int, int>> starts;
    queue<pair<int, int>> ends;
    for (int i = 1; i <= n; i++) {
        cin >> dest[i];

        if (dest[i] > dest[i - 1]) {
            starts.push({i, dest[i] - dest[i - 1]});
        }
        if (dest[i - 1] > dest[i]) {
            ends.push({i - 1, dest[i - 1] - dest[i]});
        }
    }
    if (dest[n] > 0) ends.push({n, dest[n]});

    int last = n + 1;
    for (int i = n; i > 0; i--) {
        nast[i] = last;
        if (dest[i] > dest[i - 1] || dest[i] > dest[i + 1]) {
            last = i;
        }
    }

    int dist = n;

    while (!ends.empty()) {
        // cerr << ends.front().first << " " << ends.front().second << "\n";
        while (!starts.empty() && starts.front().second <= ends.front().second) {
            // cerr << starts.front().first << "-" << ends.front().first << " " << starts.front().second << "\n";
            dist = min(dist, ends.front().first - starts.front().first + 1);
            ends.front().second -= starts.front().second;
            // cerr << "now " << ends.front().second << "\n";
            starts.pop();
        }
        // teraz więcej początków niż końców
        if (ends.front().second > 0) {
            // cerr << starts.front().first << "-" << ends.front().first << " " << ends.front().second;
            dist = min(dist, ends.front().first - starts.front().first + 1);
            starts.front().second -= ends.front().second;
        }
        ends.pop();
    }

    
    // while (!ends.empty()) {
    //     cerr << ends.front().first << " ";
    //     ends.pop();
    // }
    // cerr << "\n";


    // cerr << "dist = " << dist << "\n";
    // int diff = 0;
    // while (!starts.empty()) {
    //     diff += starts.front().second;
    //     while (diff > 0) {
    //         diff -= ends.front().second;
    //         ends.pop();
    //     }
    //     starts.pop();
    // }

    int wyn = 1;

    int len = 1;
    for (int p = 2; p <= dist; p++) {
        if (!sito[p]) {
            bool good = true;
            // vector<int> pref(n + 2, 0);
            // print(pref);

            // cerr << "testuje " << p << "\n";
            int i = 1, j = 1;
            while (i <= n) {
                // cerr << "i = " << i << "\n";

                int delta = dest[i] - pref[j];
                if (delta < 0) {
                    good = false;
                    // cerr << "za dużo\n";
                    clear(min(n, j + p));
                    break;
                } else if (delta > 0) {
                    // cerr << "za mało\n";
                    if (i + p > n + 1) {
                        good = false;
                        // cerr << "poza zakres\n";
                        clear(min(n, j + p));
                        break;
                    }
                    // cerr << "pref[" << i << "] = " << pref[i] << "\n";
                    // cerr << "pref[" << i + p * len << "] = " << pref[i + len * p] << "\n";
                    pref[j] += delta;
                    pref[j + p] -= delta;
                    // cerr << "pref[" << i << "] = " << pref[i] << "\n";
                    // cerr << "pref[" << i + p * len << "] = " << pref[i + len * p] << "\n";
                    // print(pref);
                }
                // print(pref);
                pref[j + 1] += pref[j];

                if (nast[i] - p > i + p) {
                    i += ((nast[i] - i - p - 1) / p) * p;
                }

                i++;
                j++;
            }


            if (!good) {
                for (int i = p; i <= n; i += p) {
                    sito[i] = true;
                } 
            }
            else {
                clear(n);
                wyn = p;
                // cerr << p << " OK\n";
            }
        }
    }

    cout << wyn << "\n";
    return 0;
}