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
// g++ bur.cpp  && ./a.out < test/by_me/1.in
#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>
#include <numeric>

using namespace std;

vector<long long> divisors_lower_than(long long divident, int limit)
{
    std::vector<long long> divisors;

    for (long long i = 1; i * i <= divident; ++i)
    {
        if (divident % i == 0)
        {
            if (i <= limit)
            {
                divisors.push_back(i);
            }

            // to avoid duplicates we check edge cases e.g. 6*6=36
            if ((i != divident / i) and (divident / i <= limit)) {
                divisors.push_back(divident / i);
            }
        }
    }

    return divisors;
}


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

	int n;

	cin >> n;
	vector<long long> ambers(n);

	for (int i = 0; i < n; i++)
	{
		cin >> ambers[i];
	}

    long long ambers_sum = std::accumulate(ambers.begin(), ambers.end(), decltype(ambers)::value_type(0ll));

    vector<long long> divisors = divisors_lower_than(ambers_sum, n);

    long long max_div = 1;

    for(long long div: divisors)
    {
        vector<long long> sub_amber = std::vector<long long>(ambers.begin(), ambers.begin() + div);
        bool is_valid = true;
        bool is_valid_sub_amber = true;


        for (long long i=1; i<sub_amber.size(); i++)
        {
            if (sub_amber[i-1] > sub_amber[i])
            {
                is_valid_sub_amber = false;
                break;
            }
        }

        if (!is_valid_sub_amber)
        {
            continue;
        }

        deque<long long> segments_buffer = {ambers[0]};

        for (long long i=1; i<sub_amber.size(); i++)
        {
            segments_buffer.push_back(ambers[i] - ambers[i-1]);
        }

        for (long long i=div; i<n; i++)
        {
            long long removed = segments_buffer.front();
            segments_buffer.pop_front();

            long long new_waves = ambers[i] - (ambers[i-1] - removed);

            if (new_waves < 0)
            {
                is_valid = false;
                break;
            }

            segments_buffer.push_back(new_waves);
        }

        segments_buffer.pop_front();
        while (!segments_buffer.empty())
        {
            long long x = segments_buffer.front();
            segments_buffer.pop_front();
            if (x != 0)
            {
                is_valid = false;
                break;
            }
        }

        if (is_valid and max_div < div)
        {
            max_div = div;
        }
    }

    cout << max_div << endl;

}