One day n friends gathered together to play "Mafia". During each round of the game some player must be the supervisor and other n - 1 people take part in the game. For each person we know in how many rounds he wants to be a player, not the supervisor: the i-th person wants to play ai rounds. What is the minimum number of rounds of the "Mafia" game they need to play to let each person play at least as many rounds as they want?

Input

The first line contains integer n (3 ≤ n ≤ 105). The second line contains n space-separated integers a1, a2, ..., an (1 ≤ ai ≤ 109) — the i-th number in the list is the number of rounds the i-th person wants to play.

Output

In a single line print a single integer — the minimum number of game rounds the friends need to let the i-th person play at least ai rounds.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Examples

Input

3
3 2 2


Output

4


Input

4
2 2 2 2


Output

3

Note

You don't need to know the rules of "Mafia" to solve this problem. If you're curious, it's a game Russia got from the Soviet times: http://en.wikipedia.org/wiki/Mafia_(party_game).
/*
 * Remember a 7.0 student can know more than a 10.0 student.
 * Grades don't determine intelligence, they test obedience. 
 * I Never Give Up.
 */
import java.util.*;
import java.util.Map.Entry;
import java.io.*;

import com.sun.javafx.collections.MappingChange.Map;

import static java.lang.System.out;
import static java.util.Arrays.*;
import static java.lang.Math.*;
public class ContestMain {
	private static Reader in=new Reader();
	private static StringBuilder ans=new StringBuilder();
	private static long MOD=1000000007;//10^9+7 
	private static final int N=100000; //10^5
//	private static final int LIM=26;
//	private static final double PI=3.1415;
//	private static ArrayList<Integer> v[]=new ArrayList[N];
//	private static int color[]=new int[N]; //For Graph Coloring
//	private static boolean mark[]=new boolean[N];
//	private static BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
//	private static void dfs(int node){mark[node]=true;for(int x:v[node]){if(!mark[x]){dfs(x,v);}}}
	private static long powmod(long x,long n,long m){
		if(n==0)return 1;
		else if(n%2==0)return(powmod((x*x)%m,n/2,m));
		else return (x*(powmod((x*x)%m,(n-1)/2,m)))%m;
	}
//	private static void shuffle(long [] arr) {
//		for (int i = arr.length - 1; i >= 2; i--) {
//			int x = new Random().nextInt(i - 1);
//	        long temp = arr[x];
//	        arr[x] = arr[i];
//	        arr[i] = temp;
//	    }
//	 }
//	private static void swap(int i,int j,int ar[]){
//		int temp=ar[i];
//		ar[i]=ar[j];
//		ar[j]=temp;
//	}
//	private static long gcd(long a, long b){
//		if(b==0)return a;
//		return gcd(b,a%b);
//	}
	private static Queue<node> queue=new LinkedList();
	static class node{
		int x,y,cost;
		node(int x,int y,int c){
			this.x=x;
			this.y=y;
			cost=c;
		}
	}
	private static boolean check(int x,int y,int n,int m,String ar[]){
		if((x>=0&&x<n)&&(y>=0&&y<m))return true;
		return false;
	}
	private static void bfs(int sx,int sy,int dist[][],int n,int m,String ar[]){
		node newnode=new node(sx,sy,0);
		queue.add(newnode);
		node temp;
		int x,y;
		boolean visited[][]=new boolean[n][m];
		while(!queue.isEmpty()){
			temp=queue.poll();
			x=temp.x;y=temp.y;
			if(check(x+1,y,n,m,ar)&&!visited[x+1][y]){
				dist[x+1][y]=min(dist[x+1][y],temp.cost+1);
				queue.add(new node(x+1,y,temp.cost+1));
				visited[x+1][y]=true;
			}
			if(check(x-1,y,n,m,ar)&&!visited[x-1][y]){
				dist[x-1][y]=min(dist[x-1][y],temp.cost+1);
				queue.add(new node(x-1,y,temp.cost+1));
				visited[x-1][y]=true;
			}
			if(check(x,y+1,n,m,ar)&&!visited[x][y+1]){
				dist[x][y+1]=min(dist[x][y+1],temp.cost+1);
				queue.add(new node(x,y+1,temp.cost+1));
				visited[x][y-1]=true;
			}
			if(check(x,y-1,n,m,ar)&&!visited[x][y-1]){
				dist[x][y-1]=min(dist[x][y-1],temp.cost+1);
				queue.add(new node(x,y-1,temp.cost+1));
			}
		}
	}
	private static void init(int n,int m,int dist[][],String ar[]){
		for(int i=0;i<n;i++){
			for(int j=0;j<m;j++){
				if(ar[i].charAt(j)==1)dist[i][j]=0;
				else dist[i][j]=Integer.MAX_VALUE;
			}
		}
	}
	static void swap(int a[],int index1,int index2){
		int temp=a[index1];
		a[index1]=a[index2];
		a[index2]=temp;
	}
	static void reverse(int a[],int start,int end){  //Start should be equal to k+1 but end should be less than end
		int temp;
		int temp_a[]=new int[end-start];
		for(int i=0;i<temp_a.length;i++)
			temp_a[i]=a[start++];
		for(int i=0;i<temp_a.length;i++){
			a[--end]=temp_a[i];
		}
	}
	static int next_permutation(int ar[]){
		int k=0,l=0;
		int index=0;
		while(index<ar.length-1){
			if(ar[index]<ar[index+1])k=index;
			index++;
		}
		int value=ar[k];
		for(int i=k+1;i<ar.length;i++){
			if(value<ar[i])l=i;
		}
		swap(ar,k,l);
		if(k!=l){
			reverse(ar,k+1,ar.length);
			return 1;
		}
		else return 0;
	}
	static int pos(int num){
		int cnt=0,x=0;
		while((num&x)==0){
			x=1<<cnt;
			cnt++;
		}
		return cnt;
	}

	public static void main(String[] args) throws IOException{
		int n=in.nextInt();
		long sum=0,mx=Long.MIN_VALUE,x;
		for(int i=0;i<n;i++){
			x=in.nextLong();
			sum+=x;
			mx=max(mx,x);
		}
		out.println(max(mx,(long)ceil(((double)sum)/(n-1))));
//		int t=in.nextInt();
//		int n,cnt=1;
//		long sum,mult,temp;
//		while(t-->0){
//			n=in.nextInt();
//			sum=0;
//			for(int i=1;i<=n;i++){
//				mult=n-i;
//				temp=1;
//				mult+=i-1;
//				for(int j=2;j<=n;j++){
//					temp=(temp*mult--)%MOD;
//				}
//				sum=(sum+temp)%MOD;
//			}
//			out.println("Case #"+(cnt++)+": "+sum);
//		}
//		int t=in.nextInt(),n,m,dist[][];
//		String ar[];
//		while(t-->0){
//			n=in.nextInt();
//			m=in.nextInt();
//			dist=new int[n][m];
//			ar=new String[n];
//			for(int i=0;i<n;i++)
//				ar[i]=in.next();
//			for(int i=0;i<n;i++){
//				for(int j=0;j<m;j++){
//					if(ar[i].charAt(j)=='1'){
//						init(n,m,dist,ar);
//						bfs(i,j,dist,n,m,ar);
//					}
//				}
//			}
//			for(int i=0;i<n;i++){
//				for(int j=0;j<m;j++)
//					out.print(dist[i][j]+" ");
//				out.println();
//			}
//		}
	}
	static class Pair<T> implements Comparable<Pair>{
		int l;
		int r;
		Pair(){
			l=0;
			r=0;
		}
		Pair(int k,int v){
			l=k;
			r=v;
		}
		@Override
		public int compareTo(Pair o) {
			if(o.l!=l)return (int) (l-o.l);
			else return (r-o.r);
		}
		
	}
	static class Reader{
        BufferedReader br;
        StringTokenizer st;
        public Reader()
        {
            br = new BufferedReader(new
                     InputStreamReader(System.in));
        }
 
        String next()
        {
            while (st == null || !st.hasMoreElements())
            {
                try
                {
     
                	st = new StringTokenizer(br.readLine());
                }
                catch (IOException  e)
                {
                    e.printStackTrace();
                }
            }
            return st.nextToken();
        }
 
        int nextInt()
        {
            return Integer.parseInt(next());
        }
 
        long nextLong()
        {
            return Long.parseLong(next());
        }
 
        double nextDouble()
        {
            return Double.parseDouble(next());
        }
 
        String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
    }
}