Description: 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. Input Format: 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$$$). Output Format: Print one non-negative integer — expansion coefficient of the array $$$a_1, a_2, \ldots, a_n$$$. Note: In the first test, the expansion coefficient of the array $$$[6, 4, 5, 5]$$$ is equal to $$$1$$$ because $$$|i-j| \leq min(a_i, a_j)$$$, because all elements of the array satisfy $$$a_i \geq 3$$$. On the other hand, this array isn't a $$$2$$$-extension, because $$$6 = 2 \cdot |1 - 4| \leq min(a_1, a_4) = 5$$$ is false. In the second test, the expansion coefficient of the array $$$[0, 1, 2]$$$ is equal to $$$0$$$ because this array is not a $$$1$$$-extension, but it is $$$0$$$-extension.