#pragma GCC optimize("Ofast")
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>

#define F first
#define S second
#define int long long
#define ll long long
//#define int  unsigned long long
#define pb push_back
//#define double long double

using namespace std;
using namespace __gnu_pbds;
typedef  tree< int , null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int N = 500050;
const int K = 1e18;
const int M = 1e9;
const int mod = 1e9 + 7;
int a[N], n;
int solve(){
    int res = 0;
    for (int i = (n + 1) / 2; i <= n; i++){
        multiset <int> s;
        int x = 0;
        for (int j = n; j >= i; j--){
            x += a[j] * j;
            s.insert(a[j]);
        }
        int q = s.size();
        for (int j = q; j >= 1; j--){
            x -= *s.begin() * j;
            s.erase(s.begin());
        }
        for (int j = 1; j <= q; j++){
            x -= a[j] * j;
            s.insert(a[j]);
        }
        for (int j = q + 1; j <= n; j++){
            if (j < i){
                x -= a[j] * j;
                s.insert(a[j]);
            }
            x += *s.begin() * j;
            s.erase(s.begin());
        }
        res = max(res, x);
    }
    return res;
};
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    int ans = solve();
    for (int i = 1; i <= n / 2; i++) swap(a[i], a[n - i + 1]);
    ans = max(ans, solve());
    cout << ans;
}
