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).
3
1000000000 1000000000 10000000
 3
1 2 1
 3
4 10 11
 5
1000000000 5 5 4 4
 5
1000000000 1000000000 1000000000 1000000000 1000000000
 10
94 96 91 95 99 94 96 92 95 99
 7
9 7 7 8 8 7 8
 3
1 1 1
 3
677876423 834056477 553175531
 10
13 12 10 13 13 14 10 10 12 12
 5
1000000000 1 1 1 1
 100
1 555 876 444 262 234 231 598 416 261 206 165 181 988 469 123 602 592 533 97 864 716 831 156 962 341 207 377 892 51 866 96 757 317 832 476 549 472 770 1000 887 145 956 515 992 653 972 677 973 527 984 559 280 346 580 30 372 547 209 929 492 520 446 726 47 170 699 560 814 206 688 955 308 287 26 102 77 430 262 71 415 586 532 562 419 615 732 658 108 315 268 574 86 12 23 429 640 995 342 305
 4
1 2 3 4
 3
2 1 1
 4
1000000000 1000000000 1000000000 1000000000
 30
94 93 90 94 90 91 93 91 93 94 93 90 100 94 97 94 94 95 94 96 94 98 97 95 97 91 91 95 98 96

1005000000
 2
 13
 1000000000
 1250000000
 106
 9
 2
 1032554216
 14
 1000000000
 1000
 4
 2
 1333333334
 100

// Main Code at the Bottom
import java.util.*;
import java.lang.*;
import java.io.*;
import java.math.BigInteger; 
public class Main {
	//Fast IO class
    static class FastReader {
        BufferedReader br; 
        StringTokenizer st; 
        public FastReader() {
        	boolean env=System.getProperty("ONLINE_JUDGE") != null;
        	if(!env) {
        		try {
					br=new BufferedReader(new FileReader("src\\input.txt"));
				} catch (FileNotFoundException e) {
					e.printStackTrace();
				}
        	}
        	else 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; 
        } 
    }     
    static long MOD=1000000000+7;
    //debug
    static void debug(Object... o) {
        System.out.println(Arrays.deepToString(o));
    }
    // Pair
    static class pair{
    	long x,y;
    	pair(long a,long b){
    		this.x=a;
    		this.y=b;
    	}
    	public boolean equals(Object obj) {
    		if(obj == null || obj.getClass()!= this.getClass()) return false;
            pair p = (pair) obj;
            return (this.x==p.x && this.y==p.y);
        }
    	public int hashCode() {
            return Objects.hash(x,y);
        }
    }
    static FastReader sc=new FastReader();
    static PrintWriter out=new PrintWriter(System.out);  
    //Main function(The main code starts from here)
    public static void main (String[] args) throws java.lang.Exception {
    	int test=1;
    	//test=sc.nextInt();
    	while(test-->0){
    		int n=sc.nextInt();
    		long sum=0,max=0;
    		for(int i=0;i<n;i++) {
    			long a=sc.nextLong();
    			sum+=a;
    			max=Math.max(max, a);
    		}
    		out.println(Math.max(max, (sum+n-2)/(n-1)));
    	}	
        out.flush();
        out.close();
    }
}