[AdditionalFile5687.zip](file://AdditionalFile5687.zip?type=additional_file)

#5687. 「PA 2026」Bursztyny

标签: 传统 | 时间限制: 1500 ms | 内存限制: 1024 MiB |

题目描述

题目译自 PA 2026 Runda 5 Bursztyny

每场风暴过后，Bajtocja 的海滩上都会布满琥珀。这是因为 Bajtocja 海是在一片古老森林的遗址上形成的；树脂凝固形成了琥珀，每当风暴来袭，它们就会被冲上海滩。海滩被防波堤划分为 $n$ 个路段。Bajtocja 风暴中的海浪具有有趣的特性：每一波海浪的宽度相同，且都会给恰好 $k$ 个连续的海滩路段各带来一颗琥珀。

昨天傍晚，Bajtazar 在海滩上散步。遗憾的是，那时候所有的琥珀都已经被捡走了。幸运的是，夜间发生了一场风暴，于是 Bajtazar 清晨醒来后，急忙奔向海滩。他成功统计出了海浪在每个路段冲上来的琥珀总数。Bajtazar 想知道，风暴期间海浪的最大宽度 $k$ 是多少。请帮他计算！

输入格式

第一行输入包含一个整数 $n$ $(1 \leq n \leq 100000)$，表示海滩被划分的路段数量。

第二行包含 $n$ 个整数 $a_{1}, \ldots, a_{n}$ $(0 \leq a_{i} \leq 1000000)$，表示海滩各路段上的琥珀数量。可以假设至少有一个 $a_{i}$ 的值大于 $0$。

输出格式

输出一个整数 $k$，即符合琥珀分布情况的最大海浪宽度。

样例 1

输入

8
1 2 3 4 5 5 3 1

输出

3

在第一个样例中，该琥珀布局可以由 $8$ 波宽度为 $k=3$ 的海浪形成：

宽度为 $2$ 或 $1$ 的海浪也能形成相同的布局。

样例 2

输入

2
1 3

输出

1

在第二个样例中，海浪宽度不可能是 $2$，因为宽度为 $2$ 的海浪在海滩上只有一种放置方式，即给两个路段各增加一颗琥珀（这无法匹配输入的 $1, 3$ 布局）。