#include <bits/stdc++.h>   using namespace std;   const long long linf = 1e18 + 5;   const int mod = (int)1e9 + 7;   const int logN = 17;   const int inf = 1e9;   const int N = 2e5 + 5;   int n, a[N], s;   vector<pair<long long, long long> > T[N << 2], g[N << 2];   pair<long long, long long> line[N];   long long pre[N];   int P[N << 2];   double intersect(pair<long long, long long> x, pair<long long, long long> y) {     return (y.second - x.second) * 1.0 / (x.first - y.first);   }   void add(vector<pair<long long, long long> > &T, pair<long long, long long> x) {     int s = T.size() - 1;     while (s > 0 && intersect(T[s], T[s - 1]) >= intersect(T[s], x)) {       T.pop_back();       s--;     }     T.push_back(x);   }   void init(int k, int bas, int son) {     P[k] = 0;     if (bas == son) {       T[k].clear();       g[k].clear();       T[k].push_back(line[bas]);       g[k].push_back(line[bas]);       return;     }     init((k + k), bas, (bas + son >> 1));     init((k + k + 1), (bas + son >> 1) + 1, son);     g[k].resize(g[(k + k)].size() + g[(k + k + 1)].size());     merge(g[(k + k)].begin(), g[(k + k)].end(), g[(k + k + 1)].begin(),           g[(k + k + 1)].end(), g[k].begin());     for (__typeof(g[k].begin()) it = g[k].begin(); it != g[k].end(); it++)       add(T[k], *it);     P[k] = 0;   }   long long query(int k, int bas, int son, int x, int y, long long t) {     if (bas > y || son < x) return -linf;     if (x <= bas && son <= y) {       while (P[k] < T[k].size() - 1 && intersect(T[k][P[k]], T[k][P[k] + 1]) <= t)         P[k]++;       return T[k][P[k]].first * t + T[k][P[k]].second;     }     return max(query((k + k), bas, (bas + son >> 1), x, y, t),                query((k + k + 1), (bas + son >> 1) + 1, son, x, y, t));   }   int main() {     scanf( %d , &n);     long long ans = 0;     for (int i = 1; i <= n; i++) {       scanf( %d , &a[i]);       pre[i] = pre[i - 1] + a[i];       ans += a[i] * (long long)i;     }     for (int i = 0; i <= n; i++) line[i] = make_pair(i, pre[n] - pre[i]);     init(1, 0, n);     long long res = -linf;     vector<pair<int, int> > look;     for (int i = 1; i <= n; i++) look.push_back(make_pair(a[i], i));     sort(look.begin(), look.end());     for (__typeof(look.begin()) it = look.begin(); it != look.end(); it++) {       long long left = query(1, 0, n, 0, it->second, it->first);       res = max(res, ans + left - (pre[n] - pre[it->second]) -                          it->second * (long long)it->first);       left = query(1, 0, n, it->second + 2, n, it->first);       res = max(res, ans + left - (pre[n] - pre[it->second]) -                          it->second * (long long)it->first);     }     cout << res <<   n ;     return 0;   }   