B. Коэффициент расширения массива
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Массив неотрицательных целых чисел $$$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$$$-расширением.