Массив неотрицательных целых чисел $$$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$$$.
4 6 4 5 5
1
3 0 1 2
0
4 821 500 479 717
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$$$-расширением.
| Codeforces Round 559 (Div. 2) |
|---|
| Закончено |
