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
// PA2026, @mjm, r4c-pal

#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <set>
using namespace std;
using lol = long long;
int nextInt() { int n; scanf("%d", &n); return n; }

const int N = 100000 + 9;
int a[N];

struct Block {
	int be;
	int len;
	lol sum;
};
vector<Block> v;

bool checkLen(int len) {
	for (int i = 0; i < v.size(); ++i)
		if (v[i].sum % len != 0)
			return false;
	for (int k = 0; k < v.size(); ++k) {
		int cur = 0;
		int be = v[k].be;
		int en = be + v[k].len;
		queue<pair<int, int>> q;
		for (int i = be; i <= en; ++i) {
			if (!q.empty() && q.front().first == i) {
				cur -= q.front().second;
				q.pop();
			}
			if (a[i] < cur)
				return false;
			if (a[i] == cur)
				continue;
			q.push({ i + len, a[i] - cur });
			cur = a[i];
		}
		if (cur != 0)
			return false;
	}
	return true;
}

int main() {
	int n = nextInt();
	a[0] = 0;
	a[n + 1] = 0;
	int curBe = 0;
	lol curSum = 0;
	int minLen = n + 1;
	for (int i = 1; i <= n + 1; ++i) {
		if (i <= n)
			a[i] = nextInt();
		if (0 == curSum) {
			if (0 == a[i])
				continue;
			curBe = i;
		}
		curSum += a[i];
		if (0 == a[i] && curSum > 0) {
			v.push_back({ curBe, i - curBe, curSum });
			curSum = 0;
			if (i - curBe < minLen)
				minLen = i - curBe;
		}
	}

	int res;
	for (res = minLen; res > 1; --res) {
		if (checkLen(res)) {
			break;
		}
	}
	printf("%d\n", res);

	return 0;
}