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

using namespace std;

#define REP(x,n) for(int x=0;x<(n);++x)
#define FOREACH(x, c) for(auto x = (c).begin(); x != (c).end(); ++x)

//#define DEBUG_LEVEL 10

#ifdef DEBUG_LEVEL
    #define DEBUG(level, x) {if (level <= DEBUG_LEVEL) {x}}
#else
    #define DEBUG(level, x)
#endif

const int MAX_N = 100001;
int n;
int tab[MAX_N];
int processTab[MAX_N];

set<int> divisors;

int optimizeMaxLength() {
    int positiveIndex = 0;
    int negativeIndex = 0;
    int balance = 0;
    int minLength = n;
    for (int positiveIndex = 0; positiveIndex < n; ++positiveIndex) {
        if (positiveIndex == 0) {
            if (tab[0] > 0) {
                balance += tab[0];
            }
        } else if (tab[positiveIndex] > tab[positiveIndex-1]) {
            balance += tab[positiveIndex] - tab[positiveIndex-1];
            while (balance > 0) {
                while (tab[negativeIndex+1] >= tab[negativeIndex]) {
                    ++negativeIndex;
                }
                balance += tab[negativeIndex+1] - tab[negativeIndex];
                ++negativeIndex;
            }
            DEBUG(3, cerr << "  Found match for " << positiveIndex << " in " << negativeIndex << "; balance is " << balance << endl;)
            minLength = min(minLength, negativeIndex - positiveIndex);
        } else if (tab[positiveIndex] == tab[positiveIndex-1] && balance < 0) {
            DEBUG(3, cerr << "  Found half-match for " << positiveIndex << " in " << negativeIndex << "; balance is " << balance << endl;)
            minLength = min(minLength, negativeIndex - positiveIndex);
        }
    }
    DEBUG(1, cerr << "optimizeMaxIndex = " << minLength << endl;)
    return minLength;
}

int inline safeGet(int index) {
    return index<0 ? 0 : processTab[index];
}

bool canSolve(int length) {
    int current = 0;
    DEBUG(2, cerr << "Trying to solve with length " << length << endl;)

    REP(x,n+1) {
        processTab[x]=0;
        DEBUG(3, cerr << "  Checking index " << x << " - tab[x]=" << tab[x] << ", current is " << current << endl;)
        current -= max(0, safeGet(x - length));
        DEBUG(4,
            if (safeGet(x - length) > 0) {
                cerr << "    current decreased by " << safeGet(x - length) << " to " << current << endl;
            }
        )
        if (tab[x] > current) {
            processTab[x] = tab[x]-current;
            current = tab[x];
            DEBUG(4, cerr << "    current increased by " << processTab[x] << " to " << current << endl;)
        } else if (tab[x] < current) {
            DEBUG(1, cerr << "  Checking " << length << " failed at index " << x << " - expected at least " << current << " but got " << tab[x] << endl;)
            return false;
        }
    }

    return true;
}

int main() {
    cin>>n;
    long long sum = 0;
    int maxA = 0;
    REP(x,n) {
        cin >> tab[x];
        sum += tab[x];
        maxA = max(maxA, tab[x]);
    }

    int lMax = sum / maxA;
    int optimizedLMax = optimizeMaxLength();
    int limit = min((int)sqrt(sum), min(lMax, optimizedLMax));
    DEBUG(0,
        cerr << "sum = " << sum << ", aMax = " << maxA << ", lMax = " << lMax << ", limit = " << limit << endl;
    )
    lMax = min(lMax, optimizedLMax);

    for (int i=1; i <= limit; ++i) {
        if (sum % i == 0) {
            divisors.insert(i);
            if ((sum/i) <= lMax) {
                divisors.insert(sum/i);
            }
        }
    }

    DEBUG(0,
        cerr << "divisors to check:";
        for(auto it = divisors.rbegin(); it != divisors.rend(); ++it) {
            cerr << " " << *it;
        }
        cerr << endl;
    )

    for(auto it = divisors.rbegin(); it != divisors.rend(); ++it) {
        if (canSolve(*it)) {
            cout << *it << endl;
            return 0;
        }
    }

    return 0;
}