Let's call an array of non-negative integers a_1, a_2, …, a_n 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(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, …, a_n. Find its expansion coefficient.

Input

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

Output

Print one non-negative integer — expansion coefficient of the array a_1, a_2, …, 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| ≤ min(a_i, a_j), because all elements of the array satisfy a_i ≥ 3. On the other hand, this array isn't a 2-extension, because 6 = 2 ⋅ |1 - 4| ≤ 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.
import java.io.*;
import java.util.*;

public class Main {
     //static ArrayList a[]=new ArrayList[3000001];
    
     public static void main(String[]args) throws IOException
    {
       InputReader in=new InputReader(System.in);
       PrintWriter pw=new PrintWriter(System.out);
       int n=in.nextInt();
       long a[]=new long [n];
       pair p[]=new pair[n];
       for(int i=0;i<n;i++)
       {
    	   a[i]=in.nextLong();
    	   p[i]=new pair(a[i],i);
       }
       Arrays.sort(p);
       long  maxi=-1,mini=-1;
       long ans=Long.MAX_VALUE;
       for(int i=n-1;i>=0;i--) {
    	   if(maxi==-1 ) {
    		   maxi=p[i].y;
    		   mini=p[i].y;
    	   }
    	  
    	   long diff=Math.max(Math.abs(maxi-p[i].y), Math.abs(mini-p[i].y));
    	   long val=p[i].x;
    	   maxi=Math.max(maxi, p[i].y);
    	   mini=Math.min(mini, p[i].y);
    	   if(diff!=0)
    	   ans=Math.min(ans, Math.floorDiv(val, diff));
       }
       pw.println(ans);
      
       pw.flush();
       pw.close();
    }
    private static void debug(Object... o) {
        System.out.println(Arrays.deepToString(o));
    }
   static class InputReader 
        {
        private final InputStream stream;
        private final byte[] buf = new byte[8192];
        private int curChar, snumChars;
        private SpaceCharFilter filter;
 
        public InputReader(InputStream stream) 
        { 
            this.stream = stream;
        }
        public int snext() 
        {
            if (snumChars == -1)
                throw new InputMismatchException();
            if (curChar >= snumChars) 
            {
                curChar = 0;
                try 
                {
                    snumChars = stream.read(buf);
                } 
                
                catch (IOException e) 
                {
                    throw new InputMismatchException();
                }
                
                if (snumChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }
 
        public int nextInt() 
        {
            int c = snext();
            while (isSpaceChar(c)) 
            {
                c = snext();
            }
            int sgn = 1;
            if (c == '-')
            {
                sgn = -1;
                c = snext();
            }
            int res = 0;
            do 
            {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = snext();
            } while (!isSpaceChar(c));
            return res * sgn;
        }
 
        public long nextLong()
        {
            int c = snext();
            while (isSpaceChar(c)) 
            {
                c = snext();
            }
            int sgn = 1;
            if (c == '-') 
            {
                sgn = -1;
                c = snext();
            }
            long res = 0;
            do 
            {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = snext();
            } while (!isSpaceChar(c));
            return res * sgn;
        }
 
        public int[] nextIntArray(int n) 
        {
            int a[] = new int[n];
            for (int i = 0; i < n; i++) 
            {
                a[i] = nextInt();
            }
            return a;
        }
        static class tri implements Comparable<tri> {
            int p, c, l;
 
            tri(int p, int c, int l) {
                this.p = p;
                this.c = c;
                this.l = l;
            }
 
            public int compareTo(tri o) {
                return Integer.compare(l, o.l);
            }
        }
 
        public String readString()
        {
            int c = snext();
            while (isSpaceChar(c)) 
            {
                c = snext();
            }
            StringBuilder res = new StringBuilder();
            do 
            {
                res.appendCodePoint(c);
                c = snext();
            } while (!isSpaceChar(c));
            return res.toString();
        }
 
        public String nextLine() 
        {
            int c = snext();
            while (isSpaceChar(c))
                c = snext();
            StringBuilder res = new StringBuilder();
            do 
            {
                res.appendCodePoint(c);
                c = snext();
            } while (!isEndOfLine(c));
            return res.toString();
        }
 
        public boolean isSpaceChar(int c) 
        {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
 
        private boolean isEndOfLine(int c) 
        {
            return c == '\n' || c == '\r' || c == -1;
        }
 
        public interface SpaceCharFilter
        {
            public boolean isSpaceChar(int ch);
        }
    }
   public static long modularExponentiation(long x,long n,long M)
   {
       long result=1;
       while(n>0)
       {
           if(n % 2 ==1)
               result=(result%M * x%M)%M;
           x=(x%M * x%M)%M;
           n=n/2;
       }
       return result;
   }
   
   public static long modInverse(int A,int M)
   {
       return modularExponentiation(A,M-2,M);
   }
   
   public static long modInverse(long A,long M)
   {
       return modularExponentiation(A,M-2,M);
   }
   static class pair implements Comparable<pair>
   {
       Long x, y;
       pair(long x,long y)
       {
           this.x=x;
           this.y=y;
       }

       public int compareTo(pair o) {
           int result = x.compareTo(o.x);
           if(result==0)
               result = y.compareTo(o.y);

           return result;
       }

       public String toString()
       {
           return x+" "+y;
       }

       public boolean equals(Object o)
       {
           if (o instanceof pair)
          {
               pair p = (pair)o;
               return (Math.abs(p.x-x)==0 && Math.abs(p.y-y)==0);
           }
           return false;
       }

       public int hashCode()
       {
           return new Long(x).hashCode()*31 + new Long(y).hashCode();
       }
   }
    public static long GCD(long a,long b)
    {
        if(b==0)
            return a;
        else
            return GCD(b,a%b);
    }
    public static long[] shuffle(long[] a, Random gen){ 
        for(int i = 0, n = a.length;i < n;i++){ 
            int ind = gen.nextInt(n-i)+i; 
            long d = a[i]; 
            a[i] = a[ind]; 
            a[ind] = d; 
        } 
        return a; 
    }
	static class Segment{ 
		pair[] seg;
		int a[];
		int lazy[];
	    Segment (int n,int b[]){
			seg=new pair[4*n];
			lazy=new int[4*n];
			a=new int[b.length];
			a=b.clone();
		}
	    public void build(int node,int start,int end) {
	    	if(start==end) {
	    		seg[node]=new pair(a[start],start);
	    		return ;
	    	}
	    	int mid=(start+end)/2;
	    	build(2*node+1,start,mid);
	    	build(2*node+2,mid+1,end);
	    	if(seg[2*node+1].x>seg[2*node+2].x)
	    		seg[node]=seg[2*node+1];
	    	else
	    		seg[node]=seg[2*node+2];
	    }
	    public void update(int node,int start,int end,int id,int val) {
	    	if(start==end) {
	    		seg[node]=new pair(seg[node].x+val,seg[node].y);
	    		return;
	    	}
	    	int mid=(start+end)/2;
	    	if(id>=start && id<=mid) {
	    		update(2*node+1,start,mid,id,val);
	    	}
	    	else
	    		update(2*node+2,mid+1,end,id,val);
	    	if(seg[2*node+1].x>seg[2*node+2].x)
	    		seg[node]=seg[2*node+1];
	    	else
	    		seg[node]=seg[2*node+2];
	    }
	    public pair query(int node,int start,int end,int l,int r) {
	    	if(l>end || r<start)
	    		return new pair(Integer.MIN_VALUE,0);
	    	if(start>=l && end<=r)
	    		return seg[node];
	    	
	    	int  mid=(start+end)/2;
	    	pair p=query(2*node+1,start,mid,l,r);
	    	pair p1=query(2*node+2,mid+1,end,l,r);
	    	if(p.x>p1.x)
	    		return p;
	    	else
	    		return p1;
	    }
	    public void updateRange(int node,int start,int end,int l,int r,int val) {
	    	if(lazy[node]!=0) {
	    		seg[node]=new pair(lazy[node]+seg[node].x,seg[node].y);

	    		if(start!=end) {
	    			lazy[2*node+1]+=lazy[node];
	    			lazy[2*node+2]+=lazy[node];
	    		}
	    		lazy[node]=0;
	    	}
	    	if(l>end || r<start)
	    		return ;
	    	if(start>=l && end<=r) {
	    		seg[node]=new pair(val+seg[node].x,seg[node].y);
	    		if(start!=end) {
	    			lazy[2*node+1]+=val;
	    			lazy[2*node+2]+=val;
	    		}
	    		return ;
	    	}
	    	int mid=(start+end)/2;
	    	updateRange(2*node+1,start,mid,l,r,val);
	    	updateRange(2*node+2,mid+1,end,l,r,val);
	    	if(seg[2*node+1].x>seg[2*node+2].x)
	    		seg[node]=seg[2*node+1];
	    	else
	    		seg[node]=seg[2*node+2];	
	    }
	    public pair queryRange(int node,int start,int end,int l,int r) {
	    	if(l>end || r<start)
	    		return new pair(Integer.MIN_VALUE,0);
	    	if(lazy[node]!=0) {
	    		seg[node]=new pair(lazy[node]+seg[node].x,seg[node].y);
	    		if(start!=end) {
	    			lazy[2*node+1]+=lazy[node];
	    			lazy[2*node+2]+=lazy[node];
	    		}
	    		lazy[node]=0;
	    	}
	    	if(start>=l && end<=r)
	    		return seg[node];
	    	
	    	int  mid=(start+end)/2;
	    	pair p=query(2*node+1,start,mid,l,r);
	    	pair p1=query(2*node+2,mid+1,end,l,r);
	    	if(p.x>p1.x)
	    		return p;
	    	else
	    		return p1;
	    }
	    
	}
    
}