Vika has n jars with paints of distinct colors. All the jars are numbered from 1 to n and the i-th jar contains ai liters of paint of color i.

Vika also has an infinitely long rectangular piece of paper of width 1, consisting of squares of size 1 × 1. Squares are numbered 1, 2, 3 and so on. Vika decided that she will start painting squares one by one from left to right, starting from the square number 1 and some arbitrary color. If the square was painted in color x, then the next square will be painted in color x + 1. In case of x = n, next square is painted in color 1. If there is no more paint of the color Vika wants to use now, then she stops.

Square is always painted in only one color, and it takes exactly 1 liter of paint. Your task is to calculate the maximum number of squares that might be painted, if Vika chooses right color to paint the first square.

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 200 000) — the number of jars with colors Vika has.

The second line of the input contains a sequence of integers a1, a2, ..., an (1 ≤ ai ≤ 109), where ai is equal to the number of liters of paint in the i-th jar, i.e. the number of liters of color i that Vika has.

Output

The only line of the output should contain a single integer — the maximum number of squares that Vika can paint if she follows the rules described above.

Examples

Input

5
2 4 2 3 3


Output

12


Input

3
5 5 5


Output

15


Input

6
10 10 10 1 10 10


Output

11

Note

In the first sample the best strategy is to start painting using color 4. Then the squares will be painted in the following colors (from left to right): 4, 5, 1, 2, 3, 4, 5, 1, 2, 3, 4, 5.

In the second sample Vika can start to paint using any color.

In the third sample Vika should start painting using color number 5.
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Scanner;
import java.util.StringTokenizer;
import java.util.function.BiConsumer;

import java.io.IOException;
import java.io.BufferedOutputStream;
import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;


public class S {
	
	private static int inf = 1<<27;
	
	static private long ans;
	static private long count1;
	static private long count2;
	static private long tmp;
	
	private static int[][] arr;
	private static int n;
	
	private static long[] larr;
	private static int r1,r2,r3;
	private static int c1,c2,c3;
	private static int p1,p2,p3;
	private static long r;
	private static long min;
	private static long max;
	private static int d;
	private static boolean check;
		
	static class Reader {
		
		static BufferedReader reader;
		static StringTokenizer tokenizer;
		
		static void init(InputStream input) {
			reader = new BufferedReader(new InputStreamReader(input));
			tokenizer = new StringTokenizer("");
		}
		
		static String next() throws IOException {
			while(!tokenizer.hasMoreTokens()) {
				tokenizer = new StringTokenizer(reader.readLine());
			}
			return tokenizer.nextToken();
		}
		
		static int nextInt() throws IOException {
			return Integer.parseInt(next());
		}
		
		static long nextLong() throws IOException {
			return Long.parseLong(next());
		}
		
	}
	
	static class Runner {
		public int min;
		public int[] route;
		
		public Runner(int l, int val) {
			// TODO Auto-generated constructor stub
			min = val;
			route  = new int[l];
			route[0] = val;
		}
	}

	static int[] merge(int[] a, int[] b) {
		int m = a.length;
		int n = b.length;
		int [] c = new int[n+m];
		
		int j=0, k=0;
		while(j+k<m+n) {
			if(j>=m) {
				c[j+k] = b[k];
				k++;
			}
			else if(k>=n) {
				c[j+k] = a[j];
				j++;
			}
			else {
				if(a[j]<b[k]) {
					c[j+k] = a[j];
					j++;
				}
				else if(a[j]==b[k]) {
					if(a[j]<b[k]) {
						c[j+k] = a[j];
						j++;
					}
					else {
						c[j+k] = b[k];
						k++;
					}
				}
				else {
					c[j+k] = b[k];
					k++;
				}
			}
		}
		return c;
	}
	
	static int[] Msort(int[] unsorted){
		int l = unsorted.length;
		
		if(l<=1) {
			return unsorted;
		}
		
		else {
			int[] Msorted = new int[l];
			int[] m1 = new int[l/2];
			int[] m2 = new int[l-(l/2)];
			
			for(int i=0; i<l; i++) {
				if(i<l/2) {
					m1[i] = unsorted[i];
				}
				else {
					m2[i-(l/2)] = unsorted[i];
				}
			}
			
			Msorted = merge(Msort(m1), Msort(m2));		
			
			return Msorted;
		}
		
	}
	
	static Runner[] merge(Runner[] a, Runner[] b) {
		int m = a.length;
		int n = b.length;
		Runner[] c = new Runner[n+m];
		
		int j=0, k=0;
		while(j+k<m+n) {
			if(j>=m) {
				c[j+k] = b[k];
				k++;
			}
			else if(k>=n) {
				c[j+k] = a[j];
				j++;
			}
			else {
				if(a[j].min<b[k].min) {
					c[j+k] = a[j];
					j++;
				}
				else if(a[j].min==b[k].min) {
					if(a[j].min<b[k].min) {
						c[j+k] = a[j];
						j++;
					}
					else {
						c[j+k] = b[k];
						k++;
					}
				}
				else {
					c[j+k] = b[k];
					k++;
				}
			}
		}
		return c;
	}
	
	static Runner[] Msort(Runner[] unsorted){
		int l = unsorted.length;
		
		if(l<=1) {
			return unsorted;
		}
		
		else {
			Runner[] Msorted = new Runner[l];
			Runner[] m1 = new Runner[l/2];
			Runner[] m2 = new Runner[l-(l/2)];
			
			for(int i=0; i<l; i++) {
				if(i<l/2) {
					m1[i] = unsorted[i];
				}
				else {
					m2[i-(l/2)] = unsorted[i];
				}
			}
			
			Msorted = merge(Msort(m1), Msort(m2));		
			
			return Msorted;
		}
		
	}

	
	static long[] merge(long[] a, long[] b) {
		int m = a.length;
		int n = b.length;
		long [] c = new long[n+m];
		
		int j=0, k=0;
		while(j+k<m+n) {
			if(j>=m) {
				c[j+k] = b[k];
				k++;
			}
			else if(k>=n) {
				c[j+k] = a[j];
				j++;
			}
			else {
				if(a[j]<b[k]) {
					c[j+k] = a[j];
					j++;
				}
				else if(a[j]==b[k]) {
					if(a[j]<b[k]) {
						c[j+k] = a[j];
						j++;
					}
					else {
						c[j+k] = b[k];
						k++;
					}
				}
				else {
					c[j+k] = b[k];
					k++;
				}
			}
		}
		return c;
	}
	
	static long[] Msort(long[] unsorted){
		int l = unsorted.length;
		
		if(l<=1) {
			return unsorted;
		}
		
		else {
			long[] Msorted = new long[l];
			long[] m1 = new long[l/2];
			long[] m2 = new long[l-(l/2)];
			
			for(int i=0; i<l; i++) {
				if(i<l/2) {
					m1[i] = unsorted[i];
				}
				else {
					m2[i-(l/2)] = unsorted[i];
				}
			}
			
			Msorted = merge(Msort(m1), Msort(m2));		
			
			return Msorted;
		}
		
	}

	static int[][] merge_x(int[][] a, int[][] b) {
		int m = a.length;
		int n = b.length;
		int [][] c = new int[n+m][2];
		
		int j=0, k=0;
		while(j+k<m+n) {
			if(j>=m) {
				c[j+k][0] = b[k][0];
				c[j+k][1] = b[k][1];
				k++;
			}
			else if(k>=n) {
				c[j+k][0] = a[j][0];
				c[j+k][1] = a[j][1];
				j++;
			}
			else {
				if(a[j][0]<b[k][0]) {
					c[j+k][0] = a[j][0];
					c[j+k][1] = a[j][1];
					j++;
				}
				else if(a[j][0]==b[k][0]) {
					if(a[j][1]<b[k][1]) {
						c[j+k][0] = a[j][0];
						c[j+k][1] = a[j][1];
						j++;
					}
					else {
						c[j+k][0] = b[k][0];
						c[j+k][1] = b[k][1];
						k++;
					}
				}
				else {
					c[j+k][0] = b[k][0];
					c[j+k][1] = b[k][1];
					k++;
				}
			}
		}
		return c;
	}
	
	static int[][] Msort_x(int[][] unsorted){
		int l = unsorted.length;
		
		if(l<=1) {
			return unsorted;
		}
		
		else {
			int[][] Msorted = new int[l][2];
			int[][] m1 = new int[l/2][2];
			int[][] m2 = new int[l-(l/2)][2];
			
			for(int i=0; i<l; i++) {
				if(i<l/2) {
					m1[i][0] = unsorted[i][0];
					m1[i][1] = unsorted[i][1];
				}
				else {
					m2[i-(l/2)][0] = unsorted[i][0];
					m2[i-(l/2)][1] = unsorted[i][1];
				}
			}
			
			Msorted = merge_x(Msort_x(m1), Msort_x(m2));
			
			return Msorted;
		}
		
	}
	
	static int[][] merge_y(int[][] a, int[][] b) {
		int m = a.length;
		int n = b.length;
		int [][] c = new int[n+m][2];
		
		int j=0, k=0;
		while(j+k<m+n) {
			if(j>=m) {
				c[j+k][0] = b[k][0];
				c[j+k][1] = b[k][1];
				k++;
			}
			else if(k>=n) {
				c[j+k][0] = a[j][0];
				c[j+k][1] = a[j][1];
				j++;
			}
			else {
				if(a[j][1]<b[k][1]) {
					c[j+k][0] = a[j][0];
					c[j+k][1] = a[j][1];
					j++;
				}
				else if(a[j][1]==b[k][1]) {
					if(a[j][0]<b[k][0]) {
						c[j+k][0] = a[j][0];
						c[j+k][1] = a[j][1];
						j++;
					}
					else {
						c[j+k][0] = b[k][0];
						c[j+k][1] = b[k][1];
						k++;
					}
				}
				else {
					c[j+k][0] = b[k][0];
					c[j+k][1] = b[k][1];
					k++;
				}
			}
		}
		return c;
	}
	
	static int[][] Msort_y(int[][] unsorted){
		int l = unsorted.length;
		
		if(l<=1) {
			return unsorted;
		}
		
		else {
			int[][] Msorted = new int[l][2];
			int[][] m1 = new int[l/2][2];
			int[][] m2 = new int[l-(l/2)][2];
			
			for(int i=0; i<l; i++) {
				if(i<l/2) {
					m1[i][0] = unsorted[i][0];
					m1[i][1] = unsorted[i][1];
				}
				else {
					m2[i-(l/2)][0] = unsorted[i][0];
					m2[i-(l/2)][1] = unsorted[i][1];
				}
			}
			
			Msorted = merge_y(Msort_y(m1), Msort_y(m2));
			
			return Msorted;
		}
		
	}
	
	static int[][] merge_3(int[][] a, int[][] b) {
		int m = a.length;
		int n = b.length;
		int [][] c = new int[n+m][3];
		
		int j=0, k=0;
		while(j+k<m+n) {
			if(j>=m) {
				c[j+k][0] = b[k][0];
				c[j+k][1] = b[k][1];
				c[j+k][2] = b[k][2];
				k++;
			}
			else if(k>=n) {
				c[j+k][0] = a[j][0];
				c[j+k][1] = a[j][1];
				c[j+k][2] = a[j][2];
				j++;
			}
			else {
				if(a[j][0]<b[k][0]) {
					c[j+k][0] = a[j][0];
					c[j+k][1] = a[j][1];
					c[j+k][2] = a[j][2];
					j++;
				}
				else if(a[j][0]==b[k][0] && a[j][1]<b[k][1]) {
					c[j+k][0] = a[j][0];
					c[j+k][1] = a[j][1];
					c[j+k][2] = a[j][2];
					j++;
				}
				else {
					c[j+k][0] = b[k][0];
					c[j+k][1] = b[k][1];
					c[j+k][2] = b[k][2];
					k++;
				}
			}
		}
		return c;
	}
	
	
	
	static int[][] Msort_3(int[][] unsorted){
		int l = unsorted.length;
		
		if(l<=1) {
			return unsorted;
		}
		
		else {
			int[][] Msorted = new int[l][3];
			int[][] m1 = new int[l/2][3];
			int[][] m2 = new int[l-(l/2)][3];
			
			for(int i=0; i<l; i++) {
				if(i<l/2) {
					m1[i][0] = unsorted[i][0];
					m1[i][1] = unsorted[i][1];
					m1[i][2] = unsorted[i][2];
				}
				else {
					m2[i-(l/2)][0] = unsorted[i][0];
					m2[i-(l/2)][1] = unsorted[i][1];
					m2[i-(l/2)][2] = unsorted[i][2];
				}
			}
			
			Msorted = merge_3(Msort_3(m1), Msort_3(m2));
			
			return Msorted;
		}
		
	}

	public static void print2dArray(int [][] arr) {
		for(int i=0; i<arr.length; i++) {
			System.out.println(arr[i][0]+" "+arr[i][1]+" ");
		}
	}
	
	public static void printArray(long [] arr) {
		for(int i=0; i<arr.length; i++) {
			System.out.println(arr[i]+" ");
		}
	}
		
	public static void printArray(int [] arr) {
		for(int i=0; i<arr.length; i++) {
			System.out.print(arr[i]+" ");
		}
		System.out.println();
	}
	
    static boolean binarySearch(int arr[], int x, int y) 
    { 
        int l = 0, r = arr.length - 1; 
        while (l <= r) { 
            int m = l + (r - l) / 2; 
  
            // If x greater, ignore left half 
            if (arr[m] < x) 
                l = m + 1; 
  
            // If x is smaller, ignore right half 
            else if(arr[m] > y)
                r = m - 1; 
            
            else {
            	return true;
            }
        } 
  
        // if we reach here, then element was 
        // not present 
        return false; 
    } 
    
    static int gcd(int a, int b) 
    { 
        if (a == 0) 
            return b; 
        return gcd(b % a, a); 
    }

    static long gcd(long a, long b) 
    { 
        if (a == 0) 
            return b; 
        return gcd(b % a, a); 
    }

    
    static long gcd_arr(long[] arr) {
    	long gcd_a = gcd(arr[0], arr[1]);
    	
    	for(int i=2; i<arr.length && gcd_a!=1; i++) {
    		gcd_a = gcd(gcd_a ,arr[i]);
    	}
    	
    	return gcd_a;
    }
    
    private static int[] ai;
    private static int aLen;
    private static int w,m;
    
	public static void main(String[] args) throws IOException {
		
		tmp = 0;
		count1 = 0;
		count2 = 0;
		
		ans = 0;
		
		Reader.init(System.in);
		
		OutputStream out = new BufferedOutputStream(System.out);
		
		int t=1;
	//	t = Reader.nextInt();
		
		main_loop:
		for(int tn=0; tn<t; tn++) {
			
			ans=0;
			int min=Integer.MAX_VALUE;
			int n = Reader.nextInt();
			
			aLen = n;
			ai = new int[aLen];
			
			for (int i = 0; i < aLen; i++) {
				ai[i] = Reader.nextInt();
				if(ai[i]<min)
					min=ai[i];
			}
			int x=0;
			for (int i = 0; i < aLen; i++) {
				if(ai[i]==min)
					x++;
			}
			int[] aMin = new int[x];
			int j=0;
			for (int i = 0; i < aLen; i++) {
				if(ai[i]==min) {
					aMin[j] = i;
					j++;
				}
			}
			
			int y = aLen-aMin[x-1]-1;
			
			for (j = 0; j < x; j++) {
				aMin[j] += y;
			}
			
			ans = aMin[0];
			
			for (j = 1; j < x; j++) {
				int z = aMin[j]-aMin[j-1]-1;
				if(z>ans)
					ans=z;
			}
			tmp=min;
			tmp*=(long)n;
			ans+=tmp;
			
			out.write((ans+"\n").getBytes());
		}
		
		out.flush();
		out.close();
		
	}
	
	private static int[][] queue;
	private static int[][] list;
	private static int lLen;
	private static long qSum;
	private static int qS;
	private static int qE;
	private static long mUsed;
		
	private static void init(int a) {
		lLen=0;
		for(int i=0; i<aLen; i++) {
			if(ai[i]<a) {
				lLen++;
			}
		}
		
		list = new int[lLen][2];
		queue = new int[lLen][2];
		qS=0;
		qE=0;
		qSum=0;
		mUsed=0;
		
		int j=0;
		for(int i=0; i<aLen; i++) {
			if(ai[i]<a) {
				list[j][0] = i;
				list[j][1] = a-ai[i];
				j++;
			}
		}
		
	}
	
	private static void enq(int pos, int val) {
		queue[qE][0]=pos;
		queue[qE][1]=val;
		qSum +=val;
		mUsed += val;
		qE++;
	}
	
	private static void deq(int pos) {
		int x = pos+1-w;
		while(qS<qE && qSum>0 && queue[qS][0]<x) {
			qSum -= queue[qS][1];
			qS++;
		}
	}
	
	static long binSearch() 
    {
        int l = ai[0], r = ai[0];

        for(int i=1; i<aLen; i++) {
    		if(ai[i]<l) {
    			l=ai[i];
    		}
    	}
        
        r = l+m+1;

        while (l <= r) { 
            int m = l + (r - l) / 2; 
  
            // If x greater, ignore left half 
            if (possible(m)) {
            	if(possible(m+1)) {
            		l = m + 1;
            	}
            	else {
            		return m;
            	}
            }
  
            // If x is smaller, ignore right half 
            else
                r = m - 1; 
            
        } 
  
        // if we reach here, then element was 
        // not present 
        return -1; 
    }

	private static boolean possible(int a) {
		// TODO Auto-generated method stub
		init(a);
		for(int i=0; i<lLen; i++) {
						
			deq(list[i][0]);
			if(qSum<list[i][1]) {
				int val = list[i][1]-(int)qSum;
				enq(list[i][0], val);
			}
		}
		
		return mUsed<=m;
	}

}
