CF344 E

#include <bits/stdc++.h>

#define ll long long
#define ld long double
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define watch(x) cout << (#x) << " : " << x << '\n'
#define boost ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

using namespace std;

#define int ll

int n;

vector < pair<ll, ll> > slope;

ll f(ll x, int id) {
    assert(id < (int)slope.size());
    return x * slope[id].first + slope[id].second;
}

const ll INF = 1e18;

ld cross(pair<ll, ll> L, pair<ll, ll> R) {
    ld A = (ld)R.second - L.second;
    ld B = (ld)L.first - R.first;
    if (B == .0)
        return INF;
    return A / B;
}

ll get(ll x) {
    if (slope.empty())
        return -INF;
    if ((int)slope.size() == 1)
        return f(x, 0);
    if (f(x, 0) >= f(x, 1))
        return f(x, 0);
    if (f(x, (int)slope.size() - 2) <= f(x, (int)slope.size() - 1))
        return f(x, (int)slope.size() - 1);

    int l = 1, r = (int)slope.size() - 2;
    assert(l <= r);

    while (l + 1 < r) {
        int m = (l + r) >> 1;
        if (f(x, m - 1) <= f(x, m))
            l = m;
        else
            r = m;
    }

    return max(f(x, l), f(x, r));
}

void add_line(pair<ll, ll> pt) {
    int sz = (int)slope.size();

    while (sz >= 2 && cross(slope[sz - 2], pt) >= cross(slope[sz - 1], pt))
        slope.pop_back(), sz--;

    slope.push_back(pt);
}

const int N = 2e5 + 128;

ll sum[2][N];
ll pref[N], suf[N];
ll a[N];

void solve() {
    cin >> n;

    for (int i = 1; i <= n; i++)
        cin >> a[i];

    for (int i = 1; i <= n; i++) {
        pref[i] = pref[i - 1] + a[i] * i;
        sum[0][i] = sum[0][i - 1] + a[i];
    }

    for (int i = n; i >= 1; i--) {
        suf[i] = suf[i + 1] + a[i] * i;
        sum[1][i] = sum[1][i + 1] + a[i];
    }

    ll answer = pref[n];

    for (int i = 1; i <= n; i++) {
        ll current = sum[0][i - 1] + pref[n] + get(a[i]) - a[i] * i;
        answer = max(answer, current);
        add_line(make_pair(i, -sum[0][i - 1]));
    }

    slope.clear();

    for (int i = n; i >= 1; i--) {
        ll current = sum[0][i] + pref[n] + get(a[i]) - a[i] * i;
        answer = max(answer, current);
        add_line(make_pair(i, -sum[0][i]));
    }

    cout << answer << '\n';
}

int32_t main() {
    boost;
    solve();
    return 0;
}