A12643 | Expansion coefficient of the array

Let's call an array of non-negative integers $a_1, a_2, \ldots, a_n$ a $k$ -extension for some non-negative integer $k$ if for all possible pairs of indices $1 \leq i, j \leq n$ the inequality $k \cdot |i - j| \leq min(a_i, a_j)$ is satisfied. The expansion coefficient of the array $a$ is the maximal integer $k$ such that the array $a$ is a $k$ -extension. Any array is a 0-expansion, so the expansion coefficient always exists.

You are given an array of non-negative integers $a_1, a_2, \ldots, a_n$ . Find its expansion coefficient.

The first line contains one positive integer $n$ — the number of elements in the array $a$ ( $2 \leq n \leq 300\,000$ ). The next line contains $n$ non-negative integers $a_1, a_2, \ldots, a_n$ , separated by spaces ( $0 \leq a_i \leq 10^9$ ).

Print one non-negative integer — expansion coefficient of the array $a_1, a_2, \ldots, a_n$ .