让我们将一个非负整数数组 $$$a_1, a_2, \ldots, a_n$$$ 称为某个非负整数 $$$k$$$ 的扩展 $$$k$$$ 如果对于所有可能的索引对 $$$1 \leq i, j \leq n$$$ 不等式 $$$k \cdot |i - j| \leq min(a_i, a_j)$$$ 满足。数组$$$a$$$的扩展系数是最大整数$$$k$$$,使得数组$$$a$$$是$$$k$$$扩展。任何数组都是0展开,因此展开系数始终存在。
给定一个非负整数数组 $$$a_1, a_2, \ldots, a_n$$$。求其膨胀系数。
输入
第一行包含一个正整数 $$$n$$$ — 数组 $$$a$$$ 中的元素数量 ($$$2 \leq n \leq 300\,000$$$)。下一行包含 $$$n$$$ 非负整数 $$$a_1, a_2, \ldots, a_n$$$,以空格分隔 ($$$0 \leq a_i \leq 10^9$$$)。
输出
打印一个非负整数——数组 $$$a_1, a_2, \ldots, a_n$$$ 的膨胀系数。
示例
输入 #1
4 6 4 5 5
输出 #1
1
输入 #2
3 0 1 2
输出 #2
0
输入 #3
4 821 500 479 717
输出 #3
239
注意
在第一个测试中,数组 $$$[6, 4, 5, 5]$$$ 的膨胀系数等于 $$$1$$$,因为 $$$|i-j| \leq min(a_i, a_j)$$$,因为数组的所有元素都满足 $$$a_i \geq 3$$$。另一方面,这个数组不是 $$$2$$$ 扩展,因为 $$$6 = 2 \cdot |1 - 4| \leq min(a_1, a_4) = 5$$$ 为假。
在第二个测试中,数组 $$$[0, 1, 2]$$$ 的扩展系数等于 $$$0$$$,因为该数组不是 $$$1$$$-扩展,而是 $$$0$$$-扩展。