每次风暴过后，Bajtocka 海滩上总是布满了琥珀。这是因为 Bajtockie 海是在一片古老的森林遗址上形成的；树脂凝固形成了琥珀，在风暴期间被冲上海滩。海滩被防波堤分成了 $n$ 个区段。Bajtockie 风暴中的海浪具有有趣的特性：每一道海浪的宽度相同，且会为恰好 $k$ 个连续的海滩区段各带来一颗琥珀。

Bajtazar 昨天晚上在海滩上散步。不幸的是，那时所有的琥珀都已经被捡走了。幸运的是，夜里发生了一场风暴，所以 Bajtazar 一大早就醒来，急忙跑向海滩。他成功数出了每个区段中被海浪冲上来的琥珀总数。Bajtazar 想知道风暴中海浪的最大宽度 $k$ 是多少。请帮他计算出来！

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 100\,000$)，表示海滩被分成的区段数量。

第二行包含一个由 $n$ 个整数组成的序列 $a_1, \dots, a_n$ ($0 \le a_i \le 1\,000\,000$)，表示每个海滩区段上的琥珀数量。你可以假设至少有一个 $a_i$ 的值大于零。

输出格式

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

样例

输入 1

8
1 2 3 4 5 5 3 1

输出 1

3

输入 2

2
1 3

输出 2

1

说明

样例说明：在第一个测试样例中，琥珀的分布可以通过八道宽度为 $k = 3$ 的海浪形成：

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

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