1159B Expansion coefficient of the array

短命女 2022-01-31 04:53 126阅读 0赞

B. Expansion coefficient of the array

time limit per test

1 second

memory limit per test

256 megabytes

input

standard input

output

standard output

Let's call an array of non-negative integers a1,a2,…,ana1,a2,…,an a kk-extension for some non-negative integer kk if for all possible pairs of indices 1≤i,j≤n1≤i,j≤n the inequality k⋅|i−j|≤min(ai,aj)k⋅|i−j|≤min(ai,aj) is satisfied. The expansion coefficient of the array aa is the maximal integer kk such that the array aa is a kk-extension. Any array is a 0-expansion, so the expansion coefficient always exists.

You are given an array of non-negative integers a1,a2,…,ana1,a2,…,an. Find its expansion coefficient.

Input

The first line contains one positive integer nn — the number of elements in the array aa (2≤n≤3000002≤n≤300000). The next line contains nn non-negative integers a1,a2,…,ana1,a2,…,an, separated by spaces (0≤ai≤1090≤ai≤109).

Output

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

Examples

input

Copy

4
    6 4 5 5

output

Copy

input

Copy

3
    0 1 2

output

Copy

input

Copy

4
    821 500 479 717

output

Copy

239

Note

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

In the second test, the expansion coefficient of the array \[0,1,2\]\[0,1,2\] is equal to 00 because this array is not a 11-extension, but it is 00-extension.

题意：输入n，表示n个正整数，找出一个系数k，k满足所有k<=min(a\[i\],a\[j\])/|i-j|，也就是这个k是满足所有数取两个组成一对，取这一对中最小的值，然后除以下标索引差，因为是满足所有对数，那就是要让k尽量小，那就让i-j的下标索引值最大，这个题n是3\*10^5如果暴力取对数，两成循环，9\*10^9会超时。就要另辟蹊径。

题解：在计算每个数的贡献，因为对于这个数来说，如果它在一对数里面不算最小的，那它根本没影响，如果他是最小的，那么它能取到的最小值就是到两端的答案，如果当前你更新了这个答案，到最后一个位置那个数更小的话，答案也会被更新，没有影响。

#include<bits/stdc++.h>
    using namespace std;
    int main()
    {
        int n,x,ans=1<<30;
        cin>>n;
        for(int i=1;i<=n;i++)
            {
                cin>>x;
                ans=min(ans,x/max(i-1,n-i));
            }
            cout<<ans<<endl;
        return 0;
    }