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-----

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-----

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


-----Examples-----
Input
4
6 4 5 5

Output
1
Input
3
0 1 2

Output
0
Input
4
821 500 479 717

Output
239


-----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.

Difficulty: interview

Starter code:

Solutions:
n = int(input())
nums = [int(x) for x in input().split()]
ans = 10 ** 12
for idx, num in enumerate(nums):
    dist = max(idx, n - idx - 1)
    curr = num // dist
    ans = min(ans, curr)
print(ans)

def main():
    from sys import stdin, stdout

    def read():
        return stdin.readline().rstrip('\n')

    def read_array(sep=None, maxsplit=-1):
        return read().split(sep, maxsplit)

    def read_int():
        return int(read())

    def read_int_array(sep=None, maxsplit=-1):
        return [int(a) for a in read_array(sep, maxsplit)]

    def write(*args, **kwargs):
        sep = kwargs.get('sep', ' ')
        end = kwargs.get('end', '\n')
        stdout.write(sep.join(str(a) for a in args) + end)

    def write_array(array, **kwargs):
        sep = kwargs.get('sep', ' ')
        end = kwargs.get('end', '\n')
        stdout.write(sep.join(str(a) for a in array) + end)

    n = read_int()
    nums = read_int_array()
    out = nums[0]
    first = nums[0]
    for i in range(1, n):
        out = min(out, min(nums[i], first) // i)
    last = nums[-1]
    for i in range(n-2, 0, -1):
        out = min(out, min(nums[i], last) // (n-1 - i))
    write(out)

main()


def main():
    n = int(input())
    arr = list(map(int, input().split()))
    ans = 10 ** 10
    for i in range(n):
        x = i if i > n - i - 1 else n - i - 1
        ans = min(ans, arr[i] // x)
    print(ans)
main()

n = int(input())
A = list(map(int, input().split()))
k = 10 ** 10
for i in range(1, n - 1):
    k = min(k, min(A[0], A[i]) // i)
    k = min(k, min(A[-1], A[i]) // (n - i - 1))
k = min(k, min(A[0], A[-1]) // (n - 1))
print(k)

n = int(input())
arr = list(map(int, input().split()))
res = float('inf')
for i in range(1, n):
    res = min(res, min(arr[i], arr[0]) // i)
for i in range(n - 1):
    res = min(res, min(arr[i], arr[n - 1]) // (n - 1 - i))
print(res)


n = int(input())
a = list(map(int, input().split()))
ans = float('inf')
for i in range(n):
    ans = min(ans, a[i] // max(i,  n - i - 1))
print(ans)

n = int(input())
a = list(map(int, input().split()))
max1 = float('inf')
for q in range(len(a)):
    if q >= n-q-1:
        max1 = min(max1, min(a[q], a[0])//q)
    if q <= n-q-1:
        max1 = min(max1, min(a[q], a[-1]) // (n-q-1))
print(max1)


def solve(a):
    for ea in map(enumerate, (a, a[::-1])):
        next(ea)
        for i, ai in ea:
            yield ai // i


def main():
    input()
    print(min(solve(tuple(map(int, input().split())))))


main()


n=int(input())
a=list(map(int,input().split()))
k=min(a[0],a[-1])//(n-1)
for i in range(1,n-1):
    k=min(k,min(a[0],a[i])//i,min(a[i],a[-1])//(n-1-i))
print(k)


n = int(input())
nums = [int(x) for x in input().split()]
answers = set()

for i in range(n):
    cur_num = nums[i]
    furthest = max(n-i-1, i)
    answers.add(cur_num // furthest)

if answers != set():
    print (min(answers))
else:
    print (0)

n = int(input())
l = list( map( int, input().split() ) )
ans = max(l)
for i in range(n):
    ans = min( ans, l[ i ] // max( i, n - i - 1 ))
print( ans )


# CODE BEGINS HERE.................

import math

n = int(input())

a = list(map(int, input().split()))

k = math.inf
for i in range(n):
	# print(k)
	if k > a[i]//max(n - i - 1, i):
		k = a[i]//max(n - i - 1, i)
print(k)

#CODE ENDS HERE....................


n = int(input())
l = list(map(int, input().split()))
b = 10 ** 9
for i in range(0, len(l)):
    b = min(b, l[i] / max(i, n - i - 1))
print(int(b))

def read_nums():
    return [int(x) for x in input().split()]


def main():
    n, = read_nums()
    nums = read_nums()
    a = [max(n - i - 1, i) for i in range(n)]
    k = min(num // val for num, val in zip(nums, a))
    print(k)


def __starting_point():
    main()

__starting_point()

n = int(input())
a = list(map(int, input().split()))
k = float('inf')
for i in range(n):
    if i == 0:
        x = min(a[0], a[-1])
        y = n - 1
        z = x // y
        k = min(k, z)
    elif i == n - 1:
        x = min(a[0], a[-1])
        y = n - 1
        z = x // y
        k = min(k, z)
    else:
        x = min(a[i], a[0])
        y = i
        z = x // y
        k = min(k, z)
        x = min(a[i], a[-1])
        y = n - i - 1
        z = x // y
        k = min(k, z)
print(k)



n=int(input())
l1=list(map(int,input().split()))
for i in range(0,n):
    if i==0:
        ans=l1[i]//(n-1)
    else :
        x=max(n-1-i,i)
        ans=min(ans,l1[i]//x)
print(ans)

import sys

sys.stdin.readline()

ar = [int(c) for c in sys.stdin.readline().split(' ')]

n = len(ar)

calcd = [  a // (max(i, n - i - 1)) for i, a in enumerate(ar)]
sys.stdout.write(f'{min(calcd)}\n')


N = int(input())
a = list(map(int, input().split()))
ans = 10**10
a0 = a[0]
for i in range(N-1):

    ans = min(ans, (min(a0, a[i+1]))//(i+1))

ar = a[-1]
for i in range(N-1):
    ans = min(ans, (min(ar, a[i]))//(N-i-1))
print(ans)


n = int(input())
sp = list(map(int, input().split()))
k = 10 ** 9 + 1
zn1 = sp[0]
zn2 = sp[-1]

ch2 = min(sp[0], zn2) // (n - 1)
if ch2 < k:
	k = ch2

for i in range(1, n - 1):
	ch1 = min(sp[i], zn1) // i
	ch2 = min(sp[i], zn2) // (n - i - 1)
	if ch2 < k:
		k = ch2
	if ch1 < k:
		k = ch1

ch1 = min(sp[-1], zn1) // (n - 1)
if ch1 < k:
	k = ch1
print(k)


N = int(input())
ls = list(map(int, input().split()))
print(min([ls[i]//max(i, N-i-1) for i in range(N)]))


import sys

n = int(sys.stdin.readline().strip())
a = [int(item) for item in sys.stdin.readline().strip().split()]

# h_min = heapify([i for i in range(n)])
# h_max = heapify([-i for i in range(n)])
k = float('inf')
for i in range(n):
    # idx1 = heappop(h_min)
    # idx2 = heappop(h_min)
    if (i != n - 1):
        k = min(k, int(a[i] / (n - 1 - i)))
    if i:
        k = min(k, int(a[i] / i))
    # k = min(k, int(a[i] / (n - 1 - i)), int(a[i] / i))

print(k)


from sys import stdin
n=int(stdin.readline().strip())
from math import ceil
s=list(map(int,stdin.readline().strip().split()))
s1=s[::-1]
d=n-1
mn=10**20
k=10**20
while d>=n//2:
    mn=min(s1[-1],s[-1],mn)
    s1.pop()
    s.pop()
    k=min(k,mn//d)
    d-=1
print(k)



R = lambda: map(int, input().split())

n = int(input())
k = 10**9
a = list(R())
for i in range(n):
    k = min(k, a[i] / max(i, n-1-i))
print(int(k))

import sys
# sys.stdin = open("#input.txt", "r")
n = int(input())
ls = list(map(int, input().split()))

ans = sys.maxsize
for i in range(n):
	ans = min(ans,ls[i]//max(i, n-i-1))
print(ans)

n = int(input())
arr = [int(i) for i in input().split()]
ans = 1e10
for i in range(len(arr)):
    if i != 0:
        sub1 = min(arr[i], arr[0]) // i
    else:
        sub1 = 1e10
    if i != n - 1:
        sub2 = min(arr[i], arr[-1]) // (n - 1 - i)
    else:
        sub2 = 1e10
    ans = min(ans, sub1, sub2)
print(ans)