Let's call an array of non-negative integers a1,a2,…,an a k-extension for some non-negative integer k if for all possible pairs of indices 1≤i,j≤n the inequality k⋅|i−j|≤min(ai,aj) 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 a1,a2,…,an. Find its expansion coefficient.

The first line contains one positive integer n — the number of elements in the array a (2≤n≤300000). The next line contains n non-negative integers a1,a2,…,an, separated by spaces (0≤ai≤10^9).

Print one non-negative integer — expansion coefficient of the array a1,a2,…,an.

In the first test, the expansion coefficient of the array [6,4,5,5] is equal to 1 because |i−j|≤min(ai,aj), because all elements of the array satisfy ai≥3. On the other hand, this array isn't a 2-extension, because 6=2⋅|1−4|≤min(a1,a4)=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.

题解

对于数列 a1,a2,…,an，分析其中任意一项ai，考虑所有的aj >= ai（aj < ai的算在aj里面考虑了），则使得min(ai,aj) = ai，要使所有的j都满足k*|i-j| <= min(ai,aj) = ai，则对于ai来说，j应该尽量远离i，这样解出来的最大的k才是有用的（即对ai的k值的约束最紧）。显然最远的j应该是数列两端中的一端，但两端不一定大于ai。那怎么办呢？仔细一想，对于两端的情况，考虑最前端a1及最后端an：

1. 如果a1 >= ai，则对于当前ai来说，k要满足k <= ai/|i-1|（如果i == 1，则说明k值没有限制）。如果a1 < ai，则对于当前ai来说，k要满足k <= a1/|i-1| < ai/|i-1|。
2. 如果an >= ai，则对于当前ai来说，k要满足k <= ai/|i-n|（如果i == n，则说明k值没有限制）。如果an < ai，则对于当前ai来说，k要满足k <= an/|i-n| < ai/|i-n|。
3. 在所有大于等于ai的aj中，k对于ai来说要满足k <= ai/|i-j|，而|i-j| <= |i-1|或|i-j| <= |i-n|，故ai/|i-1| <= ai/|i-j|或ai/|i-n| <= ai/|i-j|。

可见，对每项ai来说，考虑两端的项所解出来的k值必定有一项是有用的（即对ai的k值的约束最紧）。

枚举每一项求解出来的有用的k值，再取最小即得到最优答案。

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 #include <cstring>

 #include <string.h>

 #include <algorithm>

 #define re register

 #define il inline

 #define ll long long

 #define ld long double

 const ll MAXN = 1e6+;

 const ll INF = 1e9;

 //快读

 il ll read()

 {

     char ch = getchar();

     ll res = , f = ;

     while(ch < '' || ch > '')

     {

         if(ch == '-')   f = -;

         ch = getchar();

     }

     while(ch >= '' && ch <= '')

     {

         res = (res<<) + (res<<) + (ch-'');

         ch = getchar();

     }

     return res*f;

 }

 ll a[MAXN];

 int main()

 {

     ll n = read();

     for(re ll i = ; i <= n; ++i)

     {

         a[i] = read();

     }

     ll k = INF;

     for(re ll i = ; i <= n; ++i)

     {

         k = std::min(i==?k:std::min(a[i],a[])/(i-),k);

         k = std::min(i==n?k:std::min(a[i],a[n])/(n-i),k);

     }

     printf("%lld\n", k);

     return ;

 }