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
#include <bits/stdc++.h>
using namespace std;
#define st first
#define nd second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define BOOST ios_base::sync_with_stdio(0), cin.tie(0)
template<typename T>
using vc = vector<T>;
using ll = long long;
using ld = long double;
using ii = pair<int, int>;

const int N = 1e5 + 5;
ll t[N];
ll pref[N];
int n;
bool check(ll x){
	if(x > n) return false;
	// printf("checking %d\n", x);
	bool ok = 1;
	for(int i=0; i<n; i++){
		if(i) pref[i] += pref[i-1];
		ll fale = t[i] - pref[i];
		if(fale < 0){
			ok = 0;
			break;
		}
		if(fale > 0){
			if(i+x > n){
				ok = 0;
				break;
			}
			pref[i] += fale;
			pref[i+x] -= fale;
		}
	}
	for(int i=0; i<=n; i++) pref[i] = 0;
	return ok;
}

int main(){
	BOOST;
	cin >> n;
	ll sum = 0;
	for(int i=0; i<n; i++){cin >> t[i]; sum += t[i];}

	vc<ll> prim;
	vc<ll> divs;
	ll sump = sum;
	for(ll i=1; i*i<=sum; i++){
		if(sum%i == 0){
			divs.pb(i);
			if(i*i<sum) divs.pb(sum/i);
		}
		if(i > 1 && sump%i == 0) prim.pb(i);
		while(i > 1 && sump%i == 0) sump /= i;
	}
	if(sump > 1) prim.pb(sump);
	sort(all(divs));

	// for(auto it : divs) cout << it << " ";
	// cout << "\n"; 
	// for(auto it : prim) cout << it << " ";
	// cout << "\n"; 

	ll ans = 0;
	int s = divs.size();
	map<ll, int> bad;
	for(int i=0; i<s; i++){
		if(!bad[divs[i]]){
			if(check(divs[i])) ans = max(ans, divs[i]);
			else bad[divs[i]] = 1;
		}
		if(bad[divs[i]]){
			for(auto it : prim){
				if(sum % (divs[i] * it) == 0) bad[divs[i]*it] = 1;
			}
		}
	}

	cout << ans << "\n";
}