631_E. Product Sum_9701
Blake is the boss of Kris, however, this doesn't spoil their friendship. They often gather at the bar to talk about intriguing problems about maximising some values. This time the problem is really special.

You are given an array a of length n. The characteristic of this array is the value <image> — the sum of the products of the values ai by i. One may perform the following operation exactly once: pick some element of the array and move to any position. In particular, it's allowed to move the element to the beginning or to the end of the array. Also, it's allowed to put it back to the initial position. The goal is to get the array with the maximum possible value of characteristic.

<image>

Input

The first line of the input contains a single integer n (2 ≤ n ≤ 200 000) — the size of the array a.

The second line contains n integers ai (1 ≤ i ≤ n, |ai| ≤ 1 000 000) — the elements of the array a.

Output

Print a single integer — the maximum possible value of characteristic of a that can be obtained by performing no more than one move.

Examples

Input

4
4 3 2 5


Output

39

Input

5
1 1 2 7 1


Output

49

Input

3
1 1 2


Output

9

Note

In the first sample, one may pick the first element and place it before the third (before 5). Thus, the answer will be 3·1 + 2·2 + 4·3 + 5·4 = 39.

In the second sample, one may pick the fifth element of the array and place it before the third. The answer will be 1·1 + 1·2 + 1·3 + 2·4 + 7·5 = 49.
import java.util.*;
import java.io.*;
import java.text.*;

public class Main {
    //SOLUTION BEGIN
    //Into the Hardware Mode
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        int N = ni();
        long[] A = new long[1+N], sum = new long[1+N];
        for(int i = 1; i<= N; i++)sum[i] = sum[i-1]+(A[i] = ni());
        long ans = 0;
        for(int i = 1; i<= N; i++)ans += A[i]*i;
        long delta = 0;
        Line[] hull = new Line[N];
        int sz = 0;
        for(int i = 1; i<= N; i++){
            if(i > 1)delta = Math.max(delta, -A[i]*i+sum[i-1]+eval(hull, sz, A[i]));
            sz = addLine(hull, sz, new Line(i, -sum[i-1]));
        }
        sz = 0;
        for(int i = N; i >= 1; i--){
            if(i < N)delta = Math.max(delta, sum[i]-i*A[i]+eval(hull, sz, -A[i]));
            sz = addLine(hull, sz, new Line(-i, -sum[i]));
        }
        pn(ans+delta);
    }
    long eval(Line[] hull, int sz, long x){
        int lo = 1, hi = sz-1;
        if(sz == 1)return hull[0].eval(x);
        while(lo+1 < hi){
            int mid = lo+(hi-lo)/2;
            if(hull[mid-1].inter(hull[mid]) <= x)lo = mid;
            else hi = mid;
        }
        if(hull[hi-1].inter(hull[hi]) <= x)lo = hi;
        return Math.max(hull[0].eval(x), hull[lo].eval(x));
    }
    int addLine(Line[] hull, int sz, Line l){
        while(sz >= 2 && useless(hull[sz-2], hull[sz-1], l))sz--;
        hull[sz++] = l;
        return sz;
    }
    boolean useless(Line l1, Line l2, Line l3){
        return (l1.c-l3.c)*(l2.m-l1.m) <= (l1.c-l2.c)*(l3.m-l1.m);
    }
    class Line{
        long m, c;
        public Line(long M, long C){
            m = M;c = C;
        }
        long eval(long x){return m*x+c;}
        double inter(Line l){return (c-l.c)*1.0/(l.m-m);}
    }
    class CHT {
        //http://codeforces.com/contest/932/submission/35323630
        public static final int MIN = -1, MAX = 1;
        public TreeSet<CHT.Line> hull;
        int type;
        boolean query = false;
        Comparator<CHT.Line> comp = new Comparator<CHT.Line>() {
            public int compare(CHT.Line a, CHT.Line b) {
                if (!query) return type * Long.compare(a.m, b.m);
                if (a.left == b.left)
                    return Long.compare(a.m, b.m);
                return Double.compare(a.left, b.left);
            }
        };
        public CHT(final int type) {
            this.type = type;
            hull = new TreeSet<>(comp);
        }
        public void add(long m, long b) {
            add(new CHT.Line(m, b));
        }
        public void add(CHT.Line a) {
            CHT.Line[] LR = {hull.lower(a), hull.ceiling(a)};
            for (int i = 0; i < 2; i++)
                if (LR[i] != null && LR[i].m == a.m) {
                    if (type == 1 && LR[i].b >= a.b)
                        return;
                    if (type == -1 && LR[i].b <= a.b)
                        return;
                    remove(LR[i]);
                }
            hull.add(a);
            CHT.Line L = hull.lower(a), R = hull.higher(a);
            if (L != null && R != null && a.inter(R) <= R.left) {
                hull.remove(a);
                return;
            }
            CHT.Line LL = (L != null) ? hull.lower(L) : null;
            CHT.Line RR = (R != null) ? hull.higher(R) : null;
            if (L != null) a.left = a.inter(L);
            if (R != null) R.left = a.inter(R);
            while (LL != null && L.left >= a.inter(LL)) {
                remove(L);
                a.left = a.inter(L = LL);
                LL = hull.lower(L);
            }
            while (RR != null && R.inter(RR) <= a.inter(RR)) {
                remove(R);
                RR.left = a.inter(R = RR);
                RR = hull.higher(R);
            }
        }
        public long query(long x) {
            CHT.Line temp = new CHT.Line(0, 0, 0);
            temp.left = x;
            query = true;
            CHT.Line cur = hull.floor(temp);
            if(cur == null)return -1*type*IINF;
            //Debug.print(x, temp, hull.floor(temp));
            long ans = cur.eval(x);
            query = false;
            return ans;
        }
        private void remove(CHT.Line x) {
            hull.remove(x);
        }
        public int size() {
            return hull.size();
        }
        public class Line {
            long m;
            long b;
            double left = Long.MIN_VALUE;
            public Line(long m, long x, long y) {
                this.m = m;
                this.b = -m * x + y;
            }
            public Line(long m, long b) {
                this.m = m;
                this.b = b;
            }
            public long eval(long x) {
                return m * x + b;
            }
            public double inter(CHT.Line x) {
                return (double) (x.b - this.b) / (double) (this.m - x.m);
            }
        }
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    void exit(boolean b){if(!b)System.exit(0);}
    static void dbg(Object... o){System.err.println(Arrays.deepToString(o));}
    final long IINF = (long)1e17;
    final int INF = (int)1e9+2;
    DecimalFormat df = new DecimalFormat("0.00000000000");
    double PI = 3.141592653589793238462643383279502884197169399, eps = 1e-8;
    static boolean multipleTC = false, memory = true, fileIO = false;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        long ct = System.currentTimeMillis();
        if (fileIO) {
            in = new FastReader("");
            out = new PrintWriter("");
        } else {
            in = new FastReader();
            out = new PrintWriter(System.out);
        }
        //Solution Credits: Taranpreet Singh
        int T = multipleTC? ni():1;
        pre();
        for (int t = 1; t <= T; t++) solve(t);
        out.flush();
        out.close();
        System.err.println(System.currentTimeMillis() - ct);
    }
    public static void main(String[] args) throws Exception{
        if(memory)new Thread(null, new Runnable() {public void run(){try{new Main().run();}catch(Exception e){e.printStackTrace();}}}, "1", 1 << 28).start();
        else new Main().run();
    }
    int[][] make(int n, int e, int[] from, int[] to, boolean f){
        int[][] g = new int[n][];int[]cnt = new int[n];
        for(int i = 0; i< e; i++){
            cnt[from[i]]++;
            if(f)cnt[to[i]]++;
        }
        for(int i = 0; i< n; i++)g[i] = new int[cnt[i]];
        for(int i = 0; i< e; i++){
            g[from[i]][--cnt[from[i]]] = to[i];
            if(f)g[to[i]][--cnt[to[i]]] = from[i];
        }
        return g;
    }
    int[][][] makeS(int n, int e, int[] from, int[] to, boolean f){
        int[][][] g = new int[n][][];int[]cnt = new int[n];
        for(int i = 0; i< e; i++){
            cnt[from[i]]++;
            if(f)cnt[to[i]]++;
        }
        for(int i = 0; i< n; i++)g[i] = new int[cnt[i]][];
        for(int i = 0; i< e; i++){
            g[from[i]][--cnt[from[i]]] = new int[]{to[i], i, 0};
            if(f)g[to[i]][--cnt[to[i]]] = new int[]{from[i], i, 1};
        }
        return g;
    }
    int find(int[] set, int u){return set[u] = (set[u] == u?u:find(set, set[u]));}
    int digit(long s){int ans = 0;while(s>0){s/=10;ans++;}return ans;}
    long gcd(long a, long b){return (b==0)?a:gcd(b,a%b);}
    int gcd(int a, int b){return (b==0)?a:gcd(b,a%b);}
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object... o){for(Object oo:o)out.print(oo+" ");}
    void pn(Object... o){for(Object oo:o)out.print(oo+" ");out.println();}
    void pni(Object... o){for(Object oo:o)out.print(oo+" ");out.println();out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }

        String nextLine() throws Exception{
            String str;
            try{
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }
            return str;
        }
    }
}
5
1 1 2 7 1
 4
4 3 2 5
 3
1 1 2
 2
1 1
 5
-1 -2 -3 -4 -5
 2
-1000000 1000000
 2
-1 -1
 2
1000000 -1000000
 4
4 1 2 3
 4
2 3 4 1
 4
2 1 3 4
 2
0 0
 6
5 7 11 83 14 999
 5
1 2 5 4 5
 4
87 213 141 1
 4
0 0 0 0
 7
0 0 0 -1 0 0 0
 5
1 2 3 4 5
 2
0 1
 5
-1 -2 -3 0 -5
 2
-1000000 1001000
 2
-2 -1
 4
2 3 0 1
 4
2 1 4 4
 6
5 11 11 83 14 999
 5
1 2 2 4 5
 4
87 414 141 1
 4
0 0 -1 0
 7
0 0 0 -1 0 1 0
 5
1 2 3 2 5
 5
1 1 3 7 1
 4
8 3 2 5
 3
1 2 2
 2
-1000000 1001010
 2
-3 -1
 4
1 1 4 4
 6
5 11 11 13 14 999
 5
1 2 2 4 0
 4
87 414 33 1
 4
0 0 -1 1
 7
0 0 0 0 0 1 0
 5
1 2 3 2 3
 3
2 2 2
 2
-6 -1
 4
2 0 -1 1
 4
1 1 1 4
 2
0 -2
 6
5 11 11 13 14 1639
 5
1 2 2 1 0
 4
87 414 33 2
 4
0 -1 -1 1
 5
1 0 3 2 3
 4
8 3 1 6
 2
-6 0
 2
1001000 -1000000
 2
1 0
 2
-1 0
 4
2 0 0 1
 2
0 -1
 5
1 1 3 7 0
 4
8 3 1 5
 2
-1 -2
 3
2 2 1
 2
-1 1
 4
2 0 -2 1

49
 39
 9
 3
 -45
 1000000
 -3
 1000000
 30
 30
 30
 0
 6517
 62
 1378
 0
 -1
 55
 2
 -25
 1002000
 -4
 17
 33
 6525
 52
 2028
 -1
 5
 48
 53
 54
 11
 1002020
 -5
 31
 6176
 36
 1812
 3
 7
 38
 12
 -8
 9
 22
 -2
 10016
 21
 1815
 1
 34
 55
 -6
 1002000
 2
 -1
 11
 -1
 52
 52
 -4
 11
 1
 7
