Массив неотрицательных целых чисел \(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\). Найдите его коэффициент расширения.
Выходные данные
Выведите одно целое число — коэффициент расширения массива \(a_1, a_2, \ldots, a_n\).
Примечание
В первом тесте коэффициент расширения массива \([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\)-расширением.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
6 4 5 5
|
1
|
|
2
|
3
0 1 2
|
0
|
|
3
|
4
821 500 479 717
|
239
|