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

	static class nodeTree
	{
		int data,start,end;
		nodeTree(int d,int s,int e)
		{
			data=d;start=s;end=e;
		}
		
	}
	static class node
	{
		int data,indx_inT=0;
		node(int d)
		{data=d;}
	}

	static int Pinf=(int)Double.POSITIVE_INFINITY,Ninf=(int)Double.NEGATIVE_INFINITY;
	static int[] a;
	static class Stree
	{
		int size;nodeTree[] arr;
		Stree(int n)
		{
			size=2*((int)Math.pow(2,(int)Math.ceil(Math.log(n)/Math.log(2))))-1;
			arr=new nodeTree[size];
		}

		void build(int low,int high,int pos)
		{
			int j=0;int leaves=(size-1)/2;int k=0;
			for(int i=leaves;i<size&&j<a.length;i++)
			{
				arr[i]=new nodeTree(a[j],j,j);
				j++;k=i;
			}
			for(int i=k+1;i<size;i++)
				arr[i]=new nodeTree(Pinf,Pinf,Pinf);
			for(int i=leaves-1;i>=0;i--)
			{
				arr[i]=new nodeTree((int)Math.min(arr[2*i+1].data,arr[2*i+2].data),arr[2*i+1].start,arr[2*i+2].end);
			}
		}
		
		int find(int qlow,int qhigh,int pos)
		{
			if(arr[pos].end<qlow||arr[pos].start>qhigh)
				return Pinf;
			else if(arr[pos].end<=qhigh && arr[pos].start>=qlow)
				return arr[pos].data;
			else
			{
				return (int)Math.min(find(qlow,qhigh,2*pos+1),find(qlow,qhigh,2*pos+2));
			}
		}
		
	}
	public static void main(String[] Rohan)throws IOException
	{
		
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		String[] s;


		int n=Integer.parseInt(br.readLine());


		s=br.readLine().split(" ");


		a=new int[n];
		for(int i=0;i<n;i++) a[i]=Integer.parseInt(s[i]);
		
		Stree tree=new Stree(n);


		tree.build(0,n-1,0);


		// for(int i=0;i<q;i++)
		// {
		// 	s=br.readLine().split(" ");
		// 	if(s[0].equals("q"))
		// 	{
		// 		System.out.println(tree.find(Integer.parseInt(s[1])-1,Integer.parseInt(s[2])-1,0));
		// 	}
		// 	else
		// 	{
		// 		tree.update(Integer.parseInt(s[1])-1,Integer.parseInt(s[2]));
				
		// 	}
		// }

		int k=Integer.MAX_VALUE;

		int left=n/2,right=n/2;

		if(n%2==0) left--;

		for(int i=1;i<=n-1;i++)
		{
			if(i<=(n/2))
			{
				k=Math.min(tree.find(0,n-1,0)/i,k);
			}
			else
			{	
				left--;
				right++;

				int mm=Math.min(tree.find(0,left,0),tree.find(right,n-1,0));
				k=Math.min(mm/i,k);

			}
		}
		
		System.out.println(k);

	}
}