题目描述

每次风暴过后，Bajtoćka 海滩上都会布满琥珀。这是因为 Bajtoćkie 海形成于一片远古森林的旧址；树脂凝固后形成琥珀，在风暴期间被冲上海滩。海滩被防波堤划分为 $n$ 个区段。Bajtoćkie 风暴中的海浪具有有趣的特性：每一道浪的宽度相同，且恰好向海滩上连续 $k$ 个区段各输送一枚琥珀。

Bajtazar 昨天傍晚在海滩上散了步。遗憾的是，那时所有的琥珀都已被人捡走。幸运的是，夜里发生了一场风暴，于是 Bajtazar 一大早便起床，飞奔至海滩。他成功地数清了海浪冲上各个区段的琥珀数量。Bajtazar 想知道，此次风暴中海浪的最大宽度 $k$ 是多少。请帮他计算出来！

输入格式

输入的第一行包含一个整数 $n$（$1 \le n \le 100000$），表示海滩被划分成的区段数量。

第二行包含 $n$ 个整数 $a_1, \ldots, a_n$（$0 \le a_i \le 1000000$），表示海滩各区段上的琥珀数量。可以假设至少有一个 $a_i$ 是正数。

输出格式

输出一个整数 $k$——与琥珀分布情况相符的最大海浪宽度。

8
1 2 3 4 5 5 3 1

3

2
1 3

1

提示

样例解释

在第一个样例测试中，琥珀的分布可由宽度为 $k = 3$ 的八道浪产生：

::::align{center} ::::

同样的分布也可以由宽度为 $2$ 或 $1$ 的海浪形成。

在第二个样例测试中，宽度为 $2$ 的海浪是不可能的，因为每道这样的海浪在海滩上只有一种放置方式，即向两个区段各添加一枚琥珀。