← 返回题目列表

Codeforces · 1159/B

B. 数组的扩展系数

中文机器翻译题面 查看原题

让我们将一个非负整数数组 $$$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$$$-扩展。